Pair Sum - Sorted
Given an array of integers nums that is sorted in non-decreasing
order, and an integer target, return the indices of the two numbers
such that they add up to target.
You may assume that each input has exactly one solution, and you may not use the same element twice. Return the two indices as a list, in increasing order.
Example 1
Input: nums = [1, 2, 4, 6, 10], target = 8
Output: [1, 3]
Explanation: nums[1] + nums[3] = 2 + 6 = 8
Example 2
Input: nums = [2, 3, 4], target = 6
Output: [0, 2]
Explanation: nums[0] + nums[2] = 2 + 4 = 6
Constraints
2 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9numsis sorted in non-decreasing order.- Exactly one valid answer exists.
Because the array is already sorted, we don't need a hash map to find
the pair — we can use two pointers starting at opposite ends. If the
sum of the values at left and right is too small, the only way to
increase it is to move left inward (since the array is sorted, that
gives us a larger value). If the sum is too large, we move right
inward to get a smaller value. If the sum matches the target, we're
done. Each comparison eliminates at least one candidate pair, so the
whole array is scanned at most once.
A naive approach would check every pair with nested loops in O(n^2) time, or use a hash map in O(n) time and O(n) space; the two-pointer approach matches the hash map's O(n) time while using O(1) extra space, taking advantage of the sorted order.
def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
left, right = 0, len(nums) - 1
while left < right:
current = nums[left] + nums[right]
if current == target:
return [left, right]
if current < target:
left += 1
else:
right -= 1
return [] # no solution found (problem guarantees one exists)
Complexity: O(n) time, since each pointer moves at most n times total. O(1) extra space, since only two index variables are used.
Share this question