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:
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.
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:
- 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.
- Iterate through the Array:
- Update
arr_sum
andideal_sum
at each index. - Compare
arr_sum
andideal_sum
. When they are equal, incrementchunks
.
- Update
Code
Java
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;
}
}
Python
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.
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:
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.
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
Java
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;
}
}
Python
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
Java
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;
}
}
Python
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)