Approach #1: Brute Force [Accepted]
Intuition and Algorithm
Let's try to find the smallest left-most chunk. If the first
k elements are
[0, 1, ..., k-1], then it can be broken into a chunk, and we have a smaller instance of the same problem.
We can check whether
k+1 elements chosen from
[0, 1, ..., n-1] are
[0, 1, ..., k] by checking whether the maximum of that choice is
Time Complexity: , where is the length of
Space Complexity: .
For more approaches, please visit the article for the companion problem Max Chunks To Make Sorted II.
Analysis written by: @awice.