Approach #1: Sliding Window [Accepted]
Intuition
Let's try to find the smallest leftmost 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 nonzero.
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 leftmost 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.