{x}
blog image

Max Chunks To Make Sorted II

You are given an integer array arr.

We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return the largest number of chunks we can make to sort the array.

 

Example 1:

Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

 

Constraints:

  • 1 <= arr.length <= 2000
  • 0 <= arr[i] <= 108

Solution Explanation:

This problem asks to find the maximum number of chunks we can split the input array arr into such that after sorting each chunk individually and concatenating them, the result is a sorted array. A naive approach would involve trying all possible partitions, which is computationally expensive. A more efficient approach uses a monotonic stack.

Intuition:

The key idea is that a chunk can be formed if the maximum value within that chunk is less than or equal to the minimum value in the next chunk. The monotonic stack helps us efficiently track the maximum values encountered so far. If we encounter a value smaller than the top of the stack, it means we need to adjust the current chunk boundaries.

Algorithm:

  1. Initialization: Start with an empty stack stk.

  2. Iteration: Iterate through the input array arr.

  3. Stack Management: For each element v in arr:

    • If the stack is empty or v is greater than or equal to the top of the stack, push v onto the stack. This means v can be part of the current chunk.
    • If v is less than the top of the stack, it implies that v belongs to a previous chunk. We need to adjust the chunk boundaries. Pop elements from the stack until we find an element that is less than or equal to v. This ensures that the current chunk's maximum value is less than or equal to the next chunk's minimum value (as represented by the remaining elements in the stack). Then, push the maximum element that was popped back onto the stack. This represents the maximum value for the adjusted chunk.

  4. Result: After processing all elements, the size of the stack represents the number of chunks.

Time Complexity: O(N), where N is the length of the input array. We iterate through the array once. While the stack operations might seem like they could lead to O(N^2) in the worst case, in reality, each element is pushed and popped at most once.

Space Complexity: O(N) in the worst case, as the stack could hold up to N elements.

Example Walkthrough (Python):

Let's trace the example arr = [2,1,3,4,4]

  • Initially, stk = []
  • v = 2: stk = [2]
  • v = 1: 1 < 2, so pop 2. stk = []. Push max(popped elements) which is 2. stk = [2]
  • v = 3: 3 >= 2, stk = [2, 3]
  • v = 4: 4 >= 3, stk = [2, 3, 4]
  • v = 4: 4 >= 4, stk = [2, 3, 4, 4]

Finally, len(stk) = 4, which is the correct answer.

The provided code in Python, Java, C++, Go, TypeScript, and Rust all implement this algorithm with minor syntactic variations. They all achieve the same time and space complexity.