Pair Sum in a Sorted Array

mediumarraystwo pointers

You have a list of integers nums sorted from smallest to largest, and an integer target.

Find two different positions i < j whose values add up to exactly target, and return them as [i, j]. If no such pair exists, return null. When several pairs work, return the one your method reaches first.

Try to do it in a single pass without any extra storage: the ordering of the list tells you which end to move after each attempt.

Constraints

2 ≤ nums.length ≤ 20
-1000 ≤ nums[i], target ≤ 1000
nums is sorted ascending. Values may repeat.

Example

nums   = [3, 6, 8, 13, 17]
target = 19
result = [1, 3]

Start with the smallest and largest values: 3 + 17 = 20 is too big, so give up on 17. Next, 3 + 13 = 16 is too small, so give up on 3. Then 6 + 13 = 19 hits the target.

nums = [1,2,4,7,11,15]target = 15expected [2,4]

Loading 3D view…

Looking for two values that sum to 15

step 1 / 36

Solution

TypeScript · line 1

function pairSum(nums: number[], target: number): number[] | null {
  let i = 0;
  let j = nums.length - 1;
  while (i < j) {
    const sum = nums[i] + nums[j];
    if (sum === target) {
      return [i, j];
    }
    if (sum < target) {
      i++;
    } else {
      j--;
    }
  }
  return null;
}