769. Max Chunks To Make Sorted

[Problem]

Array Stack Greedy Sorting Monotonic Stack

---

Intuition

• The key observation is that a chunk can end at index i if the maximum value encountered so far (maxSoFar) is equal to i.
• This ensures all values in the chunk are valid for their positions in the sorted array.

Approach

• maxSoFar: Tracks the maximum value seen so far in the array.

• cnt: Counter to store the number of valid chunks.

• For each index i:
  • Update maxSoFar as the maximum of maxSoFar and arr[i].
  • Check if maxSoFar equals i. If true, increment the chunk counter (cnt).
• Return cnt

Complexity Analysis

• Time Complexity: O(n)

• Space Complexity: O(1)

Reference Image

Logic behind the approach

Code

class Solution { 
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int maxSoFar = 0;
        int cnt = 0;

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

            if(maxSoFar == i){
                cnt += 1;
            }
        }
        return cnt;
    }
}