#769

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Max Chunks To Make Sorted

The Max Chunks To Make Sorted problem requires you to split an array into the maximum number of chunks that can be sorted independently to form a sorted array.

array stack greedy sorting monotonic stack

Problem Statement

You are given an integer array arr of length n that represents a permutation of integers in the range [0, n-1]. The goal is to split arr into the maximum number of chunks such that sorting each chunk individually and concatenating the chunks will result in the sorted version of the array.

Return the largest number of chunks you can split the array into. You may assume that all elements in arr are distinct, and the array is a permutation of the range [0, n-1].

Examples

Example 1

Input: arr = [4,3,2,1,0]

Output: 1

Splitting into two or more chunks will not return the required result. For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2

Input: arr = [1,0,2,3,4]

Output: 4

We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Constraints

n == arr.length
1 <= n <= 10
0 <= arr[i] < n
All the elements of arr are unique.

Solution Approach

Stack-based State Management

To solve this problem, use a stack to track the elements and their indices. The goal is to split the array into chunks where each chunk can be independently sorted to contribute to the final sorted array. For each element, compare it with the expected sorted value to determine the chunk boundaries.

Greedy Partitioning

Greedily split the array by finding the smallest index k for which the first k+1 elements of the array are equal to the sorted sequence [0, 1, 2, ..., k]. Then, repeat this process for the remaining elements, counting the chunks as you go.

Optimization with O(n) Time Complexity

This approach works efficiently in O(n) time complexity, as each element of the array is processed once. The space complexity is O(1) since we are not using extra space beyond the stack to store indices.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The algorithm processes each element once, resulting in a time complexity of O(n). The space complexity is O(1) because only a constant amount of extra space is used beyond the input array.

What Interviewers Usually Probe

Ability to utilize stack-based algorithms for array manipulation.
Efficient handling of greedy problems, ensuring maximum chunks are found.
Understanding of time and space complexities in algorithm design.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the required sorted order when partitioning.
Incorrectly managing chunk boundaries, leading to fewer chunks than possible.
Overcomplicating the problem by trying to solve it with nested loops or recursion.

Follow-up variants

Implement a solution where sorting within chunks takes extra time.
Handle the case when the array is already sorted.
Optimize further for larger arrays (n > 10).

FAQ

How do I approach the Max Chunks To Make Sorted problem?

The problem can be solved by using stack-based state management to split the array into chunks that can be independently sorted.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array.

How can I make sure I split the array correctly?

To split the array correctly, look for the smallest k such that the first k+1 elements are equal to the sorted sequence [0, 1, 2, ..., k].

What is the key pattern to solve Max Chunks To Make Sorted?

The key pattern is stack-based state management combined with a greedy approach to partition the array into chunks.

What are some variants of this problem?

Variants of this problem include sorting within chunks or handling larger arrays with n > 10.

terminal

Solution

Solution 1: Greedy + One Pass

Since $\textit{arr}$ is a permutation of $[0,..,n-1]$, if the maximum value $\textit{mx}$ among the numbers traversed so far is equal to the current index $i$, it means a split can be made, and the answer is incremented.

1

2

3

4

5

6

7

8

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        mx = ans = 0
        for i, v in enumerate(arr):
            mx = max(mx, v)
            if i == mx:
                ans += 1
        return ans

Solution 2: Monotonic Stack

The solution of method one has certain limitations. If there are duplicate elements in the array, the correct answer cannot be obtained.

1

2

3

4

5

6

7

8

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        mx = ans = 0
        for i, v in enumerate(arr):
            mx = max(mx, v)
            if i == mx:
                ans += 1
        return ans

Continue Practicing

#768 max chunks to make sorted ii #581 shortest unsorted continuous subarray #853 car fleet