Approach #1: Brute Force [Accepted]
Intuition and Algorithm
Let's try to find the smallest leftmost chunk. If the first k
elements are [0, 1, ..., k1]
, 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, ..., n1]
are [0, 1, ..., k]
by checking whether the maximum of that choice is k
.
Complexity Analysis

Time Complexity: , where is the length of
arr

Space Complexity: .
For more approaches, please visit the article for the companion problem Max Chunks To Make Sorted II.
Analysis written by: @awice.