Two Sum (sorted)
On a sorted array, place one pointer at each end. If the sum is too small move left up; too big, move right down. Converges to the pair in one pass.
- Category
- Two Pointers
- Time complexity
- O(n)
- Space complexity
- O(1)
Pseudocode
lo ← 0, hi ← n−1 if a[lo]+a[hi] = t: found if sum < t: lo++ if sum > t: hi−−
Reference implementation
lo, hi = 0, n - 1
while lo < hi:
s = a[lo] + a[hi]
if s == t: return lo, hi
if s < t: lo += 1
else: hi -= 1