Max Chunks To Make Sorted

Med

#0723Time: O(n^2). The outer `while` loop and the inner `for` loop result in a nested iteration over the array elements. In the worst case (e.g., `arr = [n-1, n-2, ..., 0]`), the inner loop runs `n` times for the first and only chunk.Space: O(1). We only use a few variables to store sums and counters, regardless of the input size.1 company

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Stack Monotonic Stack

Companies

Poshmark

Prompt

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].

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 = [4,3,2,1,0]
Output: 1
Explanation:
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
Explanation:
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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the array to find the end of each chunk. We greedily try to make each chunk as small as possible to maximize the total number of chunks. Starting from the beginning of the current segment, we expand the potential chunk one element at a time. At each step, we check if the current subarray forms a "valid" chunk. A chunk is valid if the set of its elements corresponds exactly to the set of its indices in the final sorted array.

Algorithm

Initialize chunks = 0 and the starting index of the current segment i = 0.
Loop while i < n:
- Initialize current_sum = 0 and expected_sum = 0.
- Start an inner loop with j from i to n-1.
  - Add arr[j] to current_sum.
  - Add j to expected_sum.
  - If current_sum equals expected_sum, a valid chunk boundary is found at j.
    - Increment chunks.
    - Update i to j + 1 to start searching for the next chunk.
    - Break the inner loop.
Return chunks.

Walkthrough

We can define a chunk starting at index i. We then search for the smallest ending index j >= i such that the subarray arr[i...j] is a permutation of the numbers {i, i+1, ..., j}. To check this condition efficiently, we can use the property that since all numbers are unique, if the sum of elements in arr[i...j] is equal to the sum of numbers from i to j, the condition is met. The algorithm proceeds as follows:

Start with the first chunk at index i = 0.
Iterate j from i to n-1. In this inner loop, maintain the sum of elements in arr[i...j] (current_sum) and the sum of indices from i to j (expected_sum).
When current_sum == expected_sum, we have found the smallest possible valid chunk arr[i...j].
We increment our chunk count, and start searching for the next chunk from index j + 1.
We repeat this process until the entire array is partitioned.

1class Solution {2    public int maxChunksToSorted(int[] arr) {3        int n = arr.length;4        int chunks = 0;5        int i = 0;6        while (i < n) {7            long currentSum = 0;8            long expectedSum = 0;9            for (int j = i; j < n; j++) {10                currentSum += arr[j];11                expectedSum += j;12                if (currentSum == expectedSum) {13                    chunks++;14                    i = j + 1;15                    break;16                }17            }18        }19        return chunks;20    }21}

Complexity

Time

O(n^2). The outer `while` loop and the inner `for` loop result in a nested iteration over the array elements. In the worst case (e.g., `arr = [n-1, n-2, ..., 0]`), the inner loop runs `n` times for the first and only chunk.

Space

O(1). We only use a few variables to store sums and counters, regardless of the input size.

Trade-offs

Pros

Conceptually straightforward greedy approach.
Doesn't require complex data structures.

Cons

Inefficient due to the nested loop structure, leading to a quadratic time complexity.

A more efficient approach observes a key property of the problem. A split is possible after an index i if and only if the maximum element in the prefix arr[0...i] is exactly i. If this condition holds, it guarantees that the prefix arr[0...i] contains all numbers from 0 to i and no other numbers, which is the requirement for a valid first chunk in a partition.

Algorithm

Initialize chunks = 0 and max_so_far = 0.
Iterate through the array arr with index i from 0 to n-1.
- Update max_so_far with the maximum value between the current max_so_far and arr[i].
- If max_so_far is equal to the current index i, it means the prefix arr[0...i] contains exactly the numbers from 0 to i. This forms a valid chunk.
  - Increment chunks.
Return the total chunks.

Walkthrough

The logic is that if we can partition the array into k chunks, C_1, C_2, ..., C_k, where C_1 = arr[0...i_1], C_2 = arr[i_1+1...i_2], etc., then after sorting, sorted(C_1) must be [0, ..., i_1], sorted(C_2) must be [i_1+1, ..., i_2], and so on. This implies that the set of elements in arr[0...i_1] must be {0, ..., i_1}. A simple way to check this is to verify if max(arr[0...i_1]) == i_1. Since arr is a permutation of [0, ..., n-1], if the maximum element in the first i_1+1 positions is i_1, then these i_1+1 elements must be exactly {0, ..., i_1}. We can iterate through the array, keeping track of the maximum value encountered so far (max_so_far). Whenever max_so_far is equal to the current index i, it signifies that we have found a valid chunk boundary. This logic extends to subsequent chunks as well, because if max(arr[0...i]) == i, then the elements in arr[0...i] are {0...i}, which means the elements in the rest of the array arr[i+1...n-1] must be {i+1...n-1}.

1class Solution {2    public int maxChunksToSorted(int[] arr) {3        int chunks = 0;4        int maxSoFar = 0;5        for (int i = 0; i < arr.length; i++) {6            maxSoFar = Math.max(maxSoFar, arr[i]);7            if (maxSoFar == i) {8                chunks++;9            }10        }11        return chunks;12    }13}

Complexity

Time

O(n). We iterate through the array only once.

Space

O(1). We only use a constant amount of extra space for variables.

Trade-offs

Pros

Highly efficient with linear time complexity.
Simple to implement.
Optimal solution for this problem.

Cons

The reasoning behind why it works might be less intuitive at first glance compared to the O(n^2) approach.

Solutions

Solution

1class Solution {2public3  int maxChunksToSorted(int[] arr) {4    int ans = 0, mx = 0;5    for (int i = 0; i < arr.length; ++i) {6      mx = Math.max(mx, arr[i]);7      if (i == mx) {8        ++ans;9      }10    }11    return ans;12  }13}

1class Solution {2public:3  int maxChunksToSorted(vector<int> &arr) {4    int ans = 0, mx = 0;5    for (int i = 0; i < arr.size(); ++i) {6      mx = max(mx, arr[i]);7      ans += i == mx;8    }9    return ans;10  }11};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem