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 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.