arrayscomplexityhashing
When do two pointers beat a hash map?
Anonymous
For a sorted array, two pointers can find a pair with a target sum in O(n) time and O(1) extra space: compare the end values, then move the left pointer up or the right pointer down. A hash map can handle unsorted input in expected O(n) time and O(n) extra space under ordinary hashing assumptions. The sorted-input condition is what makes the pointer method work.
0