The Question
Coding

Max Chunks To Make Sorted II

Given an array of integers arr (which may contain duplicates), we want to split the array into a number of contiguous chunks such that if we sort each chunk individually and concatenate them, the resulting array is sorted in non-decreasing order. Your goal is to find the maximum number of chunks that can be created to satisfy this condition. Example: Input: arr = [2, 1, 3, 4, 4] Output: 4 Explanation: We can split into [2, 1], [3], [4], [4]. Sorting each gives [1, 2], [3], [4], [4], which concatenated is [1, 2, 3, 4, 4]. Constraints: - 1 <= arr.length <= 10^5 - 0 <= arr[i] <= 10^8
Swift
Prefix Sum
Suffix Min
Questions & Insights

Clarifying Questions

Are there duplicate elements in the array?
Assumption: Yes, the array can contain duplicate integers. This is the general case (often referred to as "Max Chunks To Make Sorted II").
What is the range of the integers and the array length?
Assumption: The array length N can be up to 10^5, and integers can be any valid 32-bit signed integer. This implies an O(N) or O(N \log N) solution is required.
Is the input array guaranteed to be non-empty?
Assumption: If the array is empty, the result should be 0.
What defines a "chunk"?
Assumption: A chunk is a contiguous sub-segment of the original array.

Thinking Process

Core Intuition: For a split to be valid after index i, every element in the left partition arr[0...i] must be less than or equal to every element in the right partition arr[i+1...n-1].
Mathematical Condition: A cut can be made between index i and i+1 if and only if \max(\text{arr}[0...i]) \le \min(\text{arr}[i+1...n-1]).
Optimization: To efficiently check this condition for all possible split points, we can precompute prefix maximums and suffix minimums.
leftMax[i] will store the maximum value from index 0 to i.
rightMin[i] will store the minimum value from index i to n-1.
Counting Chunks: Iterate through the array. Whenever the max of the current prefix is less than or equal to the min of the remaining suffix, it means we can complete a chunk at that position.
Implementation Breakdown

Problem Set

Functional Requirements: Return the maximum number of contiguous partitions such that sorting each partition results in a fully sorted array.
Constraints:
1 \le \text{arr.length} \le 10^5
0 \le \text{arr[i]} \le 10^8
Time Complexity: O(N)
Space Complexity: O(N)

Approach

Algorithm: Prefix Max / Suffix Min Comparison
Data Structure: Two auxiliary arrays (or one array and one running variable).
Complexity:
Time: O(N) to traverse the array three times (prefix, suffix, comparison).
Space: O(N) to store the suffix minimums.

Implementation

Wrap Up

Advanced Topics

Space Optimization: We can reduce space complexity slightly by only maintaining the rightMin array. The leftMax can be tracked using a single variable as we iterate from left to right.
Monotonic Stack Approach: This problem can also be solved using a monotonic stack. We push the maximum of each chunk onto the stack. If we encounter a value smaller than the top of the stack, we merge all chunks whose maximums are greater than the current value into one chunk. This also results in O(N) time.
Readability vs. Performance: The prefix/suffix approach is generally more intuitive for interviewers to follow than the monotonic stack approach, though both are optimal O(N).