769. Max Chunks To Make Sorted

Array Stack Greedy Sorting Monotonic Stack

Time: O(n)

Space: O(1)

Intuition

The array is a permutation of 0..n-1. We can cut after index i if max(arr[0..i]) == i, meaning all elements up to i are in their correct range.

Algorithm

1Track running maximum.
2At each index i: if max == i, we can make a cut here, increment chunk count.
3Return chunk count.

Example Walkthrough

Input: [1,0,2,3,4]

1.i=0: max=1≠0. i=1: max=1=1 → chunk. i=2: max=2=2 → chunk. i=3,4 → chunks. Total=4.

Output: 4

Common Pitfalls

•Only works for permutation of 0..n-1 (no duplicates). Different approach needed for 769 vs 768.

769.cs

// Approach: Single pass tracking running maximum; whenever running max equals current index, a valid chunk boundary is found.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxChunksToSorted(int[] arr)
    {
        int noOfChunks = 0;
        int max = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            max = Math.Max(max, arr[i]);
            if (max == i)
                noOfChunks++;
        }

        return noOfChunks;
    }
}

Was this solution helpful?