Approach #1: Sliding Window [Accepted]

Intuition

Let's try to find the smallest left-most chunk.

Algorithm

Notice that if is a chunk, and is a chunk (), then is a chunk too. This shows that a greedy approach produces the highest number of chunks.

We know the array arr should end up like expect = sorted(arr). If the count of the first k elements minus the count what those elements should be is zero everywhere, then the first k elements form a valid chunk. We repeatedly perform this process.

We can use a variable nonzero to count the number of letters where the current count is non-zero.

Complexity Analysis

  • Time Complexity: , where is the length of arr

  • Space Complexity: .


Approach #2: Sorted Count Pairs [Accepted]

Intuition

As in Approach #1, let's try to find the smallest left-most chunk, where we have some expectation expect = sorted(arr)

If the elements were distinct, then it is enough to find the smallest k with max(arr[:k+1]) == expect[k], as this must mean the elements of arr[:k+1] are some permutation of expect[:k+1].

Since the elements are not distinct, this fails; but we can amend the cumulative multiplicity of each element to itself to make the elements distinct.

Algorithm

Instead of elements x, have counted elements (x, count) where count ranges from 1 to the total number of x present in arr.

Now cur will be the cumulative maximum of counted[:k+1], where we expect a result of Y = expect[k]. We count the number of times they are equal.

Complexity Analysis

  • Time Complexity: , where is the length of arr

  • Space Complexity: .


Analysis written by: @awice.