Two pointers: pair sum in sorted array
Two pointers: pair sum in sorted array
The two pointers technique sweeps two indices through a sequence at once, usually from opposite ends, to avoid a nested loop. It shines on sorted data, where the order tells you which pointer to move:
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
# too small? move left up. too big? move right down.
Because nums is sorted, raising left can only increase the sum and
lowering right can only decrease it β so each step provably moves you
toward the target. This is the classic "Two Sum II" (LeetCode #167) idea.
Your task
Write pair_sum(nums, target) where nums is sorted ascending. Return the
two 0-based indices [i, j] (with i < j) whose values add to target.
Exactly one solution exists.
pair_sum([2, 7, 11, 15], 9) # [0, 1] (2 + 7)
pair_sum([1, 2, 3, 4, 6], 10) # [3, 4] (4 + 6)
pair_sum([2, 3, 4], 6) # [0, 2] (2 + 4)
Hint: start left at the front and right at the back. If the sum is too
small move left up; if too big move right down; if exact, return them.
Tests
- front pair
- back pair
- ends meet
- negatives
- two elements (hidden)
- middle pair (hidden)
Stuck? Ask for a spark
$ Console output will appear here.