awelgorithms

Fix one index then face the rest

Updated

Three-sum fixes i, then runs opposite pointers on the suffix: L = i+1, R = n-1. The pair at L, R plus a[i] is the triple. Then i += 1 and repeat.

What to focus on

After fixing i, L starts at i+1 not 0. R starts at n-1. L and R never include i. The suffix a[i+1..] is sorted.

Worked examples

i = 0

a = [1, 4, 9], target=14
  1. fix i=0 (1)
  2. L=1, R=2
  3. 1+4+9=14

Result: triple (1, 4, 9) · L=1, R=2

i = 0 dups

a = [1, 4, 4, 9], target=9
  1. fix i=0 (1)
  2. L=1, R=3: 1+4+9=14 > 9, R=2
  3. 1+4+4=9

Result: triple (1, 4, 4) · L=1, R=2

i = 1 no pair

a = [1, 4, 9], target=14
  1. fix i=1 (4)
  2. L=2, R=2
  3. suffix has one cell

Result: no pair on the suffix

Try it

Write threeSum(a, target). a is a sorted array of integers. target is the triple sum. i is the fixed index. L is i+1. R is n-1. Return the hitting triple. On [1, 4, 9] target 14 and on [1, 4, 4, 9] targets 9 and 17.

a is sorted non-decreasing, length ≥ 3. A target triple exists.

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

LeetCode problems that use this skill