Solution


Approach 1: Next Array

Intuition

Instead of checking whether all(L <= R for L in left for R in right), let's check whether max(left) <= min(right).

Algorithm

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[3]), so maxleft[4] = max(maxleft[3], A[3]).

Similarly, min(right) for every possible right can be found in linear time.

After we have a way to query max(left) and min(right) quickly, the solution is straightforward.

Complexity Analysis

  • Time Complexity: , where is the length of A.

  • Space Complexity: .


Analysis written by: @awice.