Approach 1: Next Array
Instead of checking whether
all(L <= R for L in left for R in right), let's check whether
max(left) <= min(right).
Let's try to find
max(left) for subarrays
left = A[:1], left = A[:2], left = A[:3], ... etc. Specifically,
maxleft[i] will be the maximum of subarray
A[:i]. They are related to each other:
max(A[:4]) = max(max(A[:3]), A), so
maxleft = max(maxleft, A).
min(right) for every possible
right can be found in linear time.
After we have a way to query
min(right) quickly, the solution is straightforward.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.