769. Max Chunks To Make Sorted - Detailed Explanation

Problem Statement

Given an array arr that is a permutation of the integers in the range [0, 1, 2, …, n-1], your task is to split the array into several "chunks" (i.e., contiguous subarrays). When you sort each chunk individually and then concatenate all the chunks, the final result should be the sorted array [0, 1, 2, …, n-1]. The goal is to return the maximum number of chunks you can create.

Example Inputs & Outputs

• Example 1:
  Input: [4, 3, 2, 1, 0]
  Output: 1
  Explanation:
  The array is in reverse order. No matter how you split the array, sorting each chunk and then concatenating them will not yield more than one chunk that meets the requirement. In this case, the entire array must be taken as one chunk.

• Example 2:
  Input: [1, 0, 2, 3, 4]
  Output: 4
  Explanation:
  As you iterate from left to right:

  • At index 0, the maximum so far is 1 (which is not equal to 0), so you cannot form a chunk yet.
  • At index 1, the maximum is still 1, and now the index equals the maximum, meaning you can form one chunk from indices 0–1.
  • At indices 2, 3, and 4, the maximum equals the current index at each step, allowing you to form additional chunks.
    Hence, the maximum number of chunks is 4.

• Example 3:
  Input: [0, 1, 2, 3, 4]
  Output: 5
  Explanation:
  The array is already sorted. At every index, the maximum value encountered equals the index itself. Thus, you can split after every element to form 5 individual chunks.

Constraints

• The length of the array, n, is in the range [1, 10^5].
• arr is a permutation of [0, 1, 2, …, n-1].

Hints

1. Maintain a Running Maximum:
   As you iterate over the array, keep track of the maximum value seen so far. Since the array is a permutation of 0 to n-1, if the running maximum equals the current index, then all numbers up to that index are exactly the set {0, 1, …, i}.

2. Identify a Valid Chunk:
   When the running maximum equals the current index, you know that if you sort the subarray from the previous partition point to the current index, it will form a correctly sorted segment. This point can act as the end of a chunk.

Approaches

1. Brute Force Approach

Idea:

• Consider every possible partition of the array into subarrays.
• For each partition, sort every subarray and then check if concatenating them yields the sorted array.
• Return the partitioning that gives the maximum number of valid chunks.

Drawbacks:

• The brute force method requires checking an exponential number of splits.
• This approach is computationally infeasible for large arrays (n up to 10^5).

Optimal Approach (Using a Single Pass)

Key Observation:
Because the array is a permutation of 0 to n-1, if you traverse the array and the running maximum (the largest value seen so far) equals the current index, it indicates that all elements from the start of the current chunk are exactly the numbers from the chunk’s range. This is your signal to make a cut.

Algorithm Steps:

1. Initialize

   • A counter (chunks) to count the number of chunks.
   • A variable (currentMax) to keep track of the maximum element encountered so far.

2. Iterate through the array:

   • For each index i, update currentMax with the maximum of currentMax and arr[i].
   • If currentMax equals i, then increment chunks because the subarray from the last partition (or start) to i can form a valid chunk.

3. Return the counter value.

Visual Example (Using Example 2: [1, 0, 2, 3, 4]):

• Index 0:

  • Current element = 1
  • currentMax = max(0, 1) = 1
  • Since currentMax (1) ≠ index (0), no chunk is formed.

• Index 1:

  • Current element = 0
  • currentMax remains 1 (max(1, 0))
  • Now, currentMax equals the index (1), so one valid chunk is formed.
  • Chunks = 1

• Index 2:

  • Current element = 2
  • currentMax = max(1, 2) = 2
  • currentMax equals index (2), so form another chunk.
  • Chunks = 2

• Index 3:

  • Current element = 3
  • currentMax = max(2, 3) = 3
  • currentMax equals index (3), form another chunk.
  • Chunks = 3

• Index 4:

  • Current element = 4
  • currentMax = max(3, 4) = 4
  • currentMax equals index (4), form another chunk.
  • Chunks = 4

Code Implementations

Python Code