Move left when the pair sum is too small05.02
If a[L]+a[R] < target, every pair using this L and a smaller right is even smaller. L += 1. R stays.
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
Same skill, three traces. Read all three before you try it.
01need 13 - given
a = [1, 4, 9],target=13,L=0,R=2- walk
L=0,R=21+9=10<13L+=1- result
L=1,R=2
02need 10 from inner - given
a = [1, 4, 9],target=10,L=0,R=1- walk
L=0,R=11+4=5<10L+=1- result
L=1,R=1
03dups - given
a = [1, 4, 4, 9],target=13,L=0,R=3- walk
L=0,R=31+9=10<13L+=1- result
L=1,R=3
Write
Do
On
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.constraintsa is sorted non-decreasing, length ≥ 2. a[L]+a[R] < target. L < R.
- Two Sum II0/3 skills ready · two pointers · mediumopen
- Two Sum II0/3 skills ready · two pointers · mediumopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.