Max Chunks to Make Sorted — Greedy Max Tracking
Sanjeev SharmaAdvertisement
Problem
Split arr (permutation of [0..n-1]) into max chunks that when sorted individually produce fully sorted array.
Approach
Track running max. A chunk can end at index i if max_so_far == i.
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def maxChunksToSorted(self, arr: list[int]) -> int:
chunks=0; mx=0
for i,n in enumerate(arr):
mx=max(mx,n)
if mx==i: chunks+=1
return chunks
C++
class Solution {
public:
int maxChunksToSorted(vector<int>& arr){
int chunks=0,mx=0;
for(int i=0;i<arr.size();i++){mx=max(mx,arr[i]);if(mx==i)chunks++;}
return chunks;
}
};
Complexity
- Time: O(n) | Space: O(1)
Advertisement
