awelgorithms

Move left when the pair sum is too small

Updated

If a[L]+a[R] < target, every pair using this L and a smaller right is even smaller. L += 1. R stays.

What to focus on

After the move L is the old L+1 and R is unchanged. You discard a[L] as a left partner. The array is already sorted.

Worked examples

need 13

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

Result: L=1, R=2

need 10 from inner

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

Result: L=1, R=1

dups

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

Result: L=1, R=3

Try it

Write moveLeftIfSmall(a, L, R, target). a is a sorted array of integers. L is the left index. R is the right index. target is the pair sum. a[L]+a[R] < target. Do L += 1. Print new L, R. Return nothing. On [1, 4, 9] from (0, 2) target 13 and from (0, 1) target 10, and on [1, 4, 4, 9] from (0, 3) target 13.

a is sorted non-decreasing, length ≥ 2. a[L]+a[R] < target. L < R.

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

LeetCode problems that use this skill