Two-sum in a sorted array, in one pass

Question

You're given an array nums sorted in ascending order and a target t. Find two positions whose values add up to exactly t. Return a pair of indices that sums to t, in O(n) time and O(1) space. Be ready to justify why your pointer move never throws away a valid pair.

Accepted Answer

Put one pointer at the low end and one at the high end. Look at their sum. - If the sum is too small, the low value is the problem. It is already paired with the largest available partner (nums[hi]), and every other remaining partner is smaller, so no pair using nums[lo] can reach t. The low value is dominated: discard it by moving lo inward. - If the sum is too big, the same logic retires the high value: it is paired with the smallest available partner, so nothing can pull the sum down enough. Move hi inward. - If the sum equals t, you're done. Each step permanently retires one element, so t…

Two-sum in a sorted array, in one pass

Your answer

More Coding questions