awelgorithms

Require sorted order before facing pointers

Updated

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.

What to focus on

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

sort first

a = [4, 1, 9]
  1. not sorted: 4 > 1
  2. sort a copy

Result: a = [1, 4, 9] then L=0, R=2

already sorted

a = [1, 4, 9]
  1. 1 ≤ 4 ≤ 9
  2. facing is legal

Result: L=0, R=2

dups sorted

a = [1, 4, 4, 9]
  1. equals are allowed
  2. still nondecreasing

Result: L=0, R=3 · already sorted

Try it

Write 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.

a is an integer array of length ≥ 2 (sorted or not — that is the check).

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

LeetCode problems that use this skill