awelgorithms

Target-sum with opposite pointers

Updated

On a sorted array, L = 0 and R = n-1. If a[L]+a[R] equals target, that is the pair. If the sum is too small, L += 1. If too large, R -= 1.

What to focus on

The array is sorted. Each step moves exactly one pointer, or both after a hit. Stop when L >= R.

Worked examples

hit 10

a = [1, 4, 9], target=10
  1. L=0, R=2
  2. 1+9=10

Result: (1, 9) at (0, 2)

hit 13

a = [1, 4, 9], target=13
  1. L=0, R=2: 1+9=10 < 13, L=1
  2. L=1, R=2: 4+9=13

Result: (4, 9) at (1, 2)

miss 8

a = [1, 4, 9], target=8
  1. L=0, R=2: 1+9=10 > 8, R=1
  2. 1+4=5 < 8, L=1
  3. L==R stop

Result: no pair

Try it

Write twoSumSorted(a, target). a is a sorted array of integers. target is the pair sum. L is the left index, start 0. R is the right index, start n-1. Return the hitting pair. Target 10 must yield (1, 9). On [1, 4, 9] with targets 10, 13, and 5.

a is sorted non-decreasing, length ≥ 2. A target pair exists.

practise it with Awel find your weak spots: free skill check

LeetCode problems that use this skill