Require sorted order before facing pointers05.01
Opposite-end sum motion is correct only on a sorted array. If a is unsorted, sort a copy first. Facing [4, 1, 9] as if it were sorted lies about which end is smaller.
Before L = 0, R = n-1 for sums, a[i] ≤ a[i+1] for every i. Unsorted input is a precondition failure, not a slightly worse scan. This skill is that check.
worked examples
Same skill, three traces. Read all three before you try it.
01sort first - given
a = [4, 1, 9]- walk
not sorted:
4>1sort a copy
- result
a = [1, 4, 9]thenL=0,R=2
02already sorted - given
a = [1, 4, 9]- walk
1≤4≤9facing is legal
- result
L=0,R=2
03dups sorted - given
a = [1, 4, 4, 9]- walk
equals are allowed
still nondecreasing
- result
L=0,R=3· already sorted
Write
If
On
ensureSorted(a).a is an integer array, sorted or not. L and R are opposite-end indices used only after a is nondecreasing.If
a is not sorted, sort a copy. Then you may set L=0, R=n-1. Print the array used for facing.On
[4, 1, 9] sort first. On [1, 4, 9] already sorted. On [1, 4, 4, 9] equals are allowed.constraintsa is an integer array of length ≥ 2 (sorted or not — that is the check).
- 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.