Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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.

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

One of the naive approaches would be to try putting a partition at every possible index in the array. For each partition configuration, sort the resulting chunks and concatenate them. Finally, check if the concatenated result matches the expected sorted array.

The time complexity of this is O(2^n * n log n):

  • Generating all partitions results in O(2^(n-1)) combinations.
  • Sorting each partition configuration takes O(n log n).
  • Comparing with the expected sorted array takes O(n).
  • Overall time complexity: O(2^n * n log n).

Method 2 - Using Prefix sum

To solve the problem of dividing the array into the maximum number of chunks that when individually sorted and concatenated result in a sorted array, we can leverage the concept of prefix sums. The prefix sum helps determine valid chunks by comparing the sum of the elements up to a certain index with the sum of the indices up to the same index. If these sums match, we can conclude that all elements up to that index can form a valid chunk.

Approach

Here is the approach:

  1. Initialize Variables:
    • arr_sum to store the sum of the array elements up to the current index.
    • ideal_sum to store the sum of the indices up to the current index.
    • chunks to count the number of valid chunks.
  2. Iterate through the Array:
    • Update arr_sum and ideal_sum at each index.
    • Compare arr_sum and ideal_sum. When they are equal, increment chunks.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        arr_sum = 0
        ideal_sum = 0
        chunks = 0
        
        for i in range(len(arr)):
            arr_sum += arr[i]
            ideal_sum += i
            if arr_sum == ideal_sum:
                chunks += 1
        
        return chunks

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 3 - Track the Max so Far

We can partition the array into contiguous segments such that each chunk, once sorted, can be concatenated to form the sorted array.

1
2
3

arr: [1, 0, 2, 4, 3]
cut :   [1, 0, 2 | 4, 3]
# [1, 0, 2] and [4, 3] are both continuous sequences.

Lets look at max array:

1

max = [1, 1, 2, 4, 4]

When max[index] == index, all values before index must be smaller than max[index]. This forms a continuous chunk as the array contains distinct numbers ranging from 0 to arr.length - 1.

Since the numbers in the array only range from [0, 1, ..., arr.length - 1], the greatest number of elements smaller than arr[k] would be arr[k] - 1, which are [0, 1, ..., arr[k] - 1]. Therefore, if arr[k] is the maximum value in [arr[0], arr[1], ..., arr[k]], all k-1 preceding numbers must lie within [0, 1, ..., arr[k] - 1], forming a continuous sequence.

1
2
3
4
5
6

array: [1, 0, 2, 4, 3]
cut :   [1, 0, 2 | 4, 3]
max:  [1, 1, 2 | 4, 4]
index:[0, 1, 2, 3, 4]
  # max[2] == 2, meaning that for the first three numbers, all values in [0, 1, 2, 3, 4] less than 2 are [0, 1].
 # Thus, [1, 0, 2] forms a continuous unordered sequence, which can be sorted into [0, 1, 2] and used to build the sorted array [0, 1, 2, 3, 4].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public int maxChunksToSorted(int[] arr) {
        if (arr == null || arr.length == 0) {
	        return 0;
	    }
        int n = arr.length;
        
        int[] max = new int[n];
        max[0] = arr[0];

        // Fill the max array to keep track of the maximum value up to each index
        for (int i = 1; i < n; i++) {
            max[i] = Math.max(max[i - 1], arr[i]);
        }
        
        int count = 0;
        // Count the chunks
        for (int i = 0; i < n; i++) {
            if (max[i] == i) {
                count++;
            }
        }
        
        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n: int = len(arr)
        if n == 0:
            return 0
        
        max_arr: List[int] = [0] * n
        max_arr[0] = arr[0]

        # Fill the max array to keep track of the maximum value up to each index
        for i in range(1, n):
            max_arr[i] = max(max_arr[i - 1], arr[i])
            
        count: int = 0
        # Count the chunks
        for i in range(n):
            if max_arr[i] == i:
                count += 1
                
        return count

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 4 - No need of using max array

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

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

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)