Data Structures19 sections · 729 units
Open in Course

Pattern - Complement Lookup

Find the other half

For two-sum, you're looking for pairs (x,y)(x, y) where x+y=targetx + y = target. So y=targetxy = target - x. For each element xx:

1.1. Check if targetxtarget - x is in the hash map

2.2. If yes, you found a pair

3.3. Add xx to the hash map

The hash map stores elements you've seen. For each new element, you check if its "complement" was seen before.