Max Chunks To Make Sorted Ii - Leetcode Solution

Problem Statement: Given an array of integers (not necessarily distinct), we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1: Input: [5,4,3,2,1] Output: 1 Explanation: Splitting into two or more chunks will not return the required sorted array. So, the most number of chunks we can make is 1.

Example 2: Input: [2,1,3,4,4] Output: 4 Explanation: We can split the given array into 4 chunks, each of which is, [2,1], [3], [4], and [4]. After sorting each chunk separately, we can concatenate them to get the sorted version of the original array.

Approach: To solve this problem, we will follow a two-step approach.

Step 1: Create two arrays We will create two arrays, leftMax and rightMin, of size n (length of array). Each element of both arrays will represent the maximum element from the start of the array to that index, and the minimum element from that index to the end of the array, respectively.

Step 2: Count number of chunks We can split the array into chunks such that each chunk is sorted, if the maximum element of the first chunk is smaller than or equal to the minimum element of the second chunk, and so on. We can keep track of the number of such valid chunks, and return that as the answer.

Solution:

class Solution { public: int maxChunksToSorted(vector<int>& arr) { int n = arr.size(); vector<int> leftMax(n), rightMin(n);

    leftMax[0] = arr[0];
    for(int i = 1; i < n; i++) {
        leftMax[i] = max(leftMax[i-1], arr[i]);
    }
    
    rightMin[n-1] = arr[n-1];
    for(int i = n-2; i >= 0; i--) {
        rightMin[i] = min(rightMin[i+1], arr[i]);
    }
    
    int count = 1;
    for(int i = 0; i < n-1; i++) {
        if(leftMax[i] <= rightMin[i+1]) {
            count++;
        }
    }
    
    return count;
}

};

Time Complexity: Creating both leftMax and rightMin arrays will take O(n) time. The loop to count valid chunks will also take O(n) time. Therefore, the overall time complexity of the solution is O(n).

Space Complexity: We are using two extra integer arrays of size n, one to store the maximum values from the start, and the other to store the minimum values from the end. Therefore, the space complexity of the solution is O(n).

1