# 19.12.2024 [769. Max Chunks To Make Sorted]
Maximum independent chunks to merge-sort array #medium
19.12.2024
769. Max Chunks To Make Sorted medium blog post substack youtube deep-dive
Join me on Telegram
Problem TLDR
Maximum independent chunks to merge-sort array #medium
Intuition
Let's observe when we can split the array:
// 0 1 2 3 4 5
// 1 3 4 0 2 5
// [ ][ ]
// 1 3 4 0 5 2
// [ ]
//
Some observations:
all numbers before split border should be less than the current index
we should move the border up to the maximum of the seen values
Approach
let's use
count
the problem size of
10
items hint for some brute-force DFS where we try every possible split and do the sort, however it is not the simplest way of solving
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$
Code
fun maxChunksToSorted(arr: IntArray): Int {
var max = 0
return (0..<arr.size).count {
max = max(max, arr[it])
it == max
}
}
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let mut m = 0;
(0..arr.len()).filter(|&i| {
m = m.max(arr[i]); i as i32 == m
}).count() as _
}
int maxChunksToSorted(vector<int>& arr) {
int r = 0;
for (int i = 0, m = 0; i < arr.size(); ++i) {
m = max(m, arr[i]); if (i == m) r++;
}
return r;
}