Code Implementation

class Solution:
    def maxChunksToSorted(self, arr):
        n = len(arr)
        max_left = [0] * n
        min_right = [0] * n

        max_left[0] = arr[0]
        for i in range(1, n):
            max_left[i] = max(max_left[i-1], arr[i])

        min_right[-1] = arr[-1]
        for i in range(n-2, -1, -1):
            min_right[i] = min(min_right[i+1], arr[i])

        chunks = 0
        for i in range(n-1):
            if max_left[i] <= min_right[i+1]:
                chunks += 1
        return chunks + 1
      

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        vector<int> maxLeft(n), minRight(n);
        maxLeft[0] = arr[0];
        for (int i = 1; i < n; ++i)
            maxLeft[i] = max(maxLeft[i-1], arr[i]);
        minRight[n-1] = arr[n-1];
        for (int i = n-2; i >= 0; --i)
            minRight[i] = min(minRight[i+1], arr[i]);
        int chunks = 0;
        for (int i = 0; i < n-1; ++i) {
            if (maxLeft[i] <= minRight[i+1])
                ++chunks;
        }
        return chunks + 1;
    }
};
      

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int[] maxLeft = new int[n];
        int[] minRight = new int[n];
        maxLeft[0] = arr[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = Math.max(maxLeft[i-1], arr[i]);
        }
        minRight[n-1] = arr[n-1];
        for (int i = n-2; i >= 0; i--) {
            minRight[i] = Math.min(minRight[i+1], arr[i]);
        }
        int chunks = 0;
        for (int i = 0; i < n-1; i++) {
            if (maxLeft[i] <= minRight[i+1]) {
                chunks++;
            }
        }
        return chunks + 1;
    }
}
      

var maxChunksToSorted = function(arr) {
    const n = arr.length;
    const maxLeft = Array(n);
    const minRight = Array(n);
    maxLeft[0] = arr[0];
    for (let i = 1; i < n; i++) {
        maxLeft[i] = Math.max(maxLeft[i-1], arr[i]);
    }
    minRight[n-1] = arr[n-1];
    for (let i = n-2; i >= 0; i--) {
        minRight[i] = Math.min(minRight[i+1], arr[i]);
    }
    let chunks = 0;
    for (let i = 0; i < n-1; i++) {
        if (maxLeft[i] <= minRight[i+1]) {
            chunks++;
        }
    }
    return chunks + 1;
};
      

Problem Description

You are given an array arr of integers, which may contain duplicates and are not necessarily in order. Your task is to split arr into the maximum number of "chunks" such that after sorting each chunk individually and concatenating them in order, the result is the same as sorting the entire array.

Key constraints:

• Each chunk must be a contiguous subarray.
• The elements can appear multiple times (not necessarily unique).
• The solution must maximize the number of chunks.
• All elements must be used exactly once; no element can be reused or omitted.

Thought Process

At first glance, it might seem that we could simply cut the array at every point where the current prefix is sorted, but with duplicate values or unsorted elements, that doesn't always work.

A brute-force approach would be to check every possible way to split the array and see if sorting the chunks and concatenating gives the sorted array. However, this is computationally expensive and not feasible for large arrays.

To optimize, we need a way to decide efficiently where we can safely "cut" the array into chunks. The key insight is to look for positions where everything to the left is less than or equal to everything to the right. If so, sorting the two parts separately and concatenating will give the correct order.

Solution Approach

The core idea is to find all positions where the maximum element on the left is less than or equal to the minimum element on the right. At these positions, it is safe to split the array into chunks.

• Step 1: For each index, compute the maximum value from the start up to that index (call this max_left).
• Step 2: For each index, compute the minimum value from that index to the end of the array (call this min_right).
• Step 3: For each possible split point (from index 0 to n-2), check if max_left[i] <= min_right[i+1]. If true, a chunk can end at i.
• Step 4: Count all such split points and add 1 (since the last chunk goes to the end of the array).

This approach ensures that after sorting each chunk and concatenating, the result will be the same as sorting the entire array.

Example Walkthrough

Consider the input arr = [5,4,3,2,1].
- The sorted array is [1,2,3,4,5].
- Let's compute max_left and min_right:

• max_left: [5,5,5,5,5]
• min_right: [1,1,1,1,1]

Now consider arr = [2,1,3,4,4].
- The sorted array is [1,2,3,4,4].
- max_left: [2,2,3,4,4]
- min_right: [1,1,3,4,4]
- Check splits:

• i=0: 2 > 1 (no split)
• i=1: 2 <= 3 (split possible!)
• i=2: 3 <= 4 (split possible!)
• i=3: 4 <= 4 (split possible!)

Time and Space Complexity

• Brute-force approach: Would involve generating all possible chunkings and verifying each, leading to exponential time complexity (O(2^n)), which is infeasible.
• Optimized approach (as above):
  • Computing max_left and min_right both take O(n) time.
  • Checking split points is O(n).
  • Total time complexity: O(n).
  • Space complexity: O(n) for the two auxiliary arrays.

Summary

The key to solving "Max Chunks To Make Sorted II" is to recognize that a chunk can end where all elements to the left are less than or equal to all elements to the right. By precomputing the maximums to the left and minimums to the right, we can efficiently find all valid split points in linear time. This approach is both elegant and efficient, transforming a seemingly complex problem into a straightforward linear scan with auxiliary arrays.