Given an array sorted in non-decreasing order and a target sum, return the two values that add up to the target — or an empty array if no such pair exists.
Video coming soon
We're producing a video walkthrough — check back soon.
Given an array sorted in non-decreasing order and a target sum, return the two values that add up to the target — or an empty array if no such pair exists.
The direct sorted-array counterpart to Two Sum: instead of a hash map trading space for one-pass lookup, sortedness lets two converging pointers find the pair in-place with no extra memory.
Whenever an array is sorted and you need two elements that hit an exact target sum, converging pointers from both ends let you decide which side to move using just one comparison — no hash set required.
This problem's return contract is the two matching values, not their indices — unlike Two Sum, sortedness makes values themselves unambiguous to work with and keeps the pointer logic focused on the sum comparison rather than index bookkeeping. Start a left pointer at index 0 and a right pointer at the last index. At each step, compare nums[left] + nums[right] to the target: if they're equal, that pair is the answer. If the sum is smaller than the target, the only way to increase it (since the array is sorted) is to move left forward. If the sum is larger, move right backward. If the pointers cross without ever matching, no pair exists, so return an empty array.
class Solution {
public int[] pairSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] { nums[left], nums[right] };
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
}