Two Sum

Easyhash mapAmazonGoogleMeta

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Input:nums = [2,7,11,15], target = 9

Output:[0,1]

Hint 1

Use a hash map to store the elements and their indices.

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Use a hash map to look up the complement (target - num) in O(1) time while iterating through the array.

Time ComplexityO(N)

Why:

Iterates through the array of N elements once, performing O(1) hash map lookups and insertions for complements.

Space ComplexityO(N)

Why:

In the worst case where no matching pair is found until the end, the hash map stores up to N elements.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🔍 Dry Run

Solution⏱ O(N) | 💾 O(N)

Key

Value

Map is empty