Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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.

Solution

Method 1 - Track max element

Here is the approach:

  1. Maintain Maximum Value Up to Current Index: Track the maximum value encountered up to each index while iterating through the array.
  2. Identify Chunks: When the maximum value equals the current index, it means all previous elements can form a valid chunk because they include all necessary integers up to that point.
  3. Track Chunks: Each time the above condition is met, increment the count of chunks.

Code

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

public class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int[] max = new int[n];
        int count = 0;

        max[0] = arr[0];
        for (int i = 1; i < n; i++) {
            max[i] = Math.max(max[i - 1], arr[i]);
        }

        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

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

        for i in range(1, n):
            max_arr[i] = max(max_arr[i - 1], arr[i])

        for i in range(n):
            if max_arr[i] == i:
                count += 1

        return count

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array. This is because the array is traversed twice.
  • 🧺 Space complexity: O(n), as an additional max[] array of the same length as the input array is used.