Algorithms and Data Structures · Middle · Question 19 of 75
Two Sum on a sorted array: what's the O(n) approach without extra memory?
- 1Binary search for the partner of every element
- 2Put all elements into a hash map before searching
- ✓Correct answer: Two pointers from both ends, moved by comparing the sum
Explanation
Sortedness tells you which pointer to move: increasing the left value raises the sum, decreasing the right value lowers it. A hash map also works in O(n) but needs O(n) memory.