Max Chunks To Make Sorted

Leetcode Problem:

• Max Chunks To Make Sorted

Summary

• Given an integer array representing a permutation of the integers in the range [0, n - 1], find the largest number of chunks we can make to sort the array.

Approach

• We use two pointers, one from the end of the array and one from the beginning, to track the maximum element seen so far in each chunk
• We also use a stack to store the elements of the current chunk
• The time complexity of this approach is O(n), where n is the length of the input array.

Complexity

• O(n)

Explanation

• We initialize a rightMin array to keep track of the maximum element seen so far in each chunk
• We iterate through the array from right to left, and for each element, we check if the stack is empty
• If it is, we push the current element onto the stack and set the rightMin value to the current index
• If the stack is not empty and the current element is less than the top of the stack, we push the current element onto the stack and set the rightMin value to the top of the stack
• If the current element is greater than or equal to the top of the stack, we set the rightMin value to the top of the stack
• We then iterate through the array from left to right, and for each element, we update the leftMax value to be the maximum of the current leftMax value and the current element
• We then check if the leftMax value is less than or equal to the rightMin value
• If it is, we increment the ans variable by 1
• Finally, we return the ans variable, which represents the largest number of chunks we can make to sort the array.

Solution Code:

class Solution {
public:
    int rightMin[10];
    vector st;
    int maxChunksToSorted(vector& arr) {
        int ans = 0;
        for(int i = arr.size()-1; i >= 0; i--){
            if(st.empty()){
                st.push_back(arr[i]);
                rightMin[i] = arr.size();
            } else if(arr[i] < st.back()){
                rightMin[i] = st.back();
                st.push_back(arr[i]);
            } else{
                rightMin[i] = st.back();
            }
        }
        int leftMax = 0;
        for(int i = 0 ; i < arr.size(); i++){
            leftMax = max(leftMax, arr[i]);
            if(leftMax <= rightMin[i]){
                ans++;
            }
        }
        return ans;
    }
};