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
- A cut after index
iis valid exactly when the set of values inarr[0..i]is precisely{0, ..., i}. - That is equivalent to
max(arr[0..i]) == i, because the prefix hasi + 1distinct values in the range[0, n-1]. - Scan left to right maintaining the running maximum; every time it equals the current index, close a chunk.
- 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_maxis at leastionce 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.