Two Sum - Algorithm Visualization

Array

Current Index (i)

Current Value

Complement (target - nums[i])

Target

HashMap (value → index)

Empty

Click "Step" or "Play" to start the visualization

Current Element

In HashMap

Solution Found

Python Code

                numsMap = dict()
            
                for i in range(len(nums)):
            
                    complement = target - nums[i]
            
                    if complement in numsMap:
            
                        return [i, numsMap[complement]]
            
                    else:
            
                        numsMap[nums[i]] = i

Complexity Analysis

Time Complexity O(n) Space Complexity O(n)

Time Complexity: O(n)

Breakdown

Single pass through array of n elements
Hash table lookup: O(1) amortized per element
Hash table insertion: O(1) amortized per element
Total operations: n lookups + n insertions = 2n

T(n) = n × (O(1) + O(1)) = O(n)

Mathematical Intuition

The naive approach compares all pairs (i, j) where i < j, yielding n(n-1)/2 = O(n²) comparisons. The hash table approach exploits the fact that for each element x, its complement target - x is uniquely determined—reducing search from O(n) to O(1).

Key Insight

We trade the nested loop's multiplicative cost for a single loop with constant-time hash operations, transforming O(n²) into O(n).

Space Complexity: O(n)

Breakdown

Hash table stores at most n entries
Each entry: one key (value) + one value (index)
No additional data structures required
Input array is not modified

S(n) = O(n) for hash table storage

Mathematical Intuition

In the worst case, we traverse the entire array before finding the solution (or determine no solution exists). At that point, the hash table contains all n elements. The space-time tradeoff is explicit: we invest O(n) space to reduce O(n) lookups from O(n) each to O(1) each.