1059. Where the Left Side Can End
A row of n values is given. Split it into a non-empty LEFT part and a
possibly empty RIGHT part, so that every value in the left part is at most every value in the
right part. Print the SHORTEST left part that works.
The whole row is always a legal left part, since the right part is then empty, so an answer
always exists and is at most n.
5 0 3 8 6 1 -> 6 no proper split works, so the left part is everything
1 1 1 0 6 12 -> 4 1 1 1 0 | 6 12
1 2 3 4 5 -> 1 1 | 2 3 4 5
5 4 3 2 1 -> 5
## What most people try first
For every length L, compute max(a[0..L-1]) and min(a[L..n-1]) and compare. Done
directly that is O(n^2), which is the brute force this problem was checked against.
Precomputing a prefix-maximum array and a suffix-minimum array fixes it: two passes, then one
comparison per L. That is a perfectly good O(n) solution using O(n) extra memory,
and it is worth writing before reading further.
## One pass, two numbers
leftMax = a[0] the maximum of the left part as currently sized
curMax = a[0] the maximum of everything seen so far
L = 1
for i in 1 .. n-1:
curMax = max(curMax, a[i])
if a[i] < leftMax:
L = i + 1 a[i] is too small to stand on the right
leftMax = curMax so swallow everything up to here
## Why swallowing everything is forced
If a[i] < leftMax, then a[i] cannot be in the right part while the current left part
stands, so the split must move past i. And once it moves past i, it must move past
EVERYTHING between the old boundary and i, because the parts are contiguous. So the new
left part is a[0..i], and its maximum is the maximum of everything seen so far, which is
curMax.
Nothing is ever undone: L only grows, and it grows only when forced. So the final L is
the smallest length no smaller than every forced move, which is the smallest legal length.
Legality at the end also has to hold, and it does: after the loop, no value after position
L - 1 is below leftMax, because any such value would have triggered a move.
## Why two maxima and not one
This is the part that is easy to get wrong. leftMax is the bar that later values must
clear. curMax is a larger, tentative maximum covering values that are not yet inside the
left part.
Using one variable for both fails on 1 0 1 0 1 0 1: the 1s raise the bar too early and the
answer comes out short. Using only leftMax and setting it to a[i] on a move fails
whenever the swallowed stretch contains something bigger than a[i], which is
1000000000 0 1000000000.
## Where this sits
Problem #851 asks for the LARGEST number of pieces the row can be cut into so that sorting each piece separately sorts the whole row. That is the same legality condition applied at every cut rather than at one, and its answer is a count rather than a position. Solving this one first makes the stack in #851 much easier to see.
## Overflow
Values fit in a signed 32 bit integer, limit 2147483647, and nothing is added. The answer
is at most n.
## Cost
Time O(n). Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer alone on a line: the length of the shortest non-empty left part such that every value in it is at most every value after it. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.