⚡Flashcard Drill➔
NeetCode #817LC-769MediumGreedy
← Back to All Problems

#817 · #769 · Max Chunks To Make Sorted(最多能完成排序的块)

📌 Problem Statement & Constraints

You are given an array arr that is a permutation of 0 .. n-1. Split the array into some number of contiguous chunks and sort each chunk individually. Return the maximum number of chunks that makes the whole array sorted. Constraints: 1 <= arr.length <= 10, arr is a permutation of 0 .. n-1.

💡 Core Algorithmic Approaches

  1. A cut after index i is valid exactly when the set of values in arr[0..i] is precisely {0, ..., i}.
  2. That is equivalent to max(arr[0..i]) == i, because the prefix has i + 1 distinct values in the range [0, n-1].
  3. Scan left to right maintaining the running maximum; every time it equals the current index, close a chunk.
  4. This greedy is optimal because cuts at all valid positions maximise the number of chunks.

💻 Benchmark Python3 Implementation

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        ans = 0
        cur_max = 0
        for i, v in enumerate(arr):
            cur_max = max(cur_max, v)
            if cur_max == i:            # prefix contains exactly {0, ..., i}
                ans += 1
        return ans

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): a running maximum and a counter.

⚠️ Interview Pitfalls & Follow-ups

  • Using cur_max >= i: since the values are a permutation, cur_max is at least i once all smaller values appear; the exact test is == i.
  • Sorting the chunks for real: the answer is the number of chunks, not the sorted array.
  • Requiring the chunk values to be consecutive starting anywhere: they must be exactly {0, ..., i}, which is why the permutation structure is essential.
  • Assuming this generalises to arbitrary arrays: for non-permutations the correct test is a prefix-sum/monotonic-stack argument, not the running maximum.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems