Leetcode 769 - Max Chunks To Make Sorted

Link to problem

Problem

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].

We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return the largest number of chunks we can make to sort the array.

Solution

This problem could be solved using monotonic stack. GOTO Monotonic Stack for some reference about the data structure.

We need a monotonic increasing stack for this one. A monotonically increasing sequence means that every element could be a chunk. By maintaing a monotonic stack, we ensure that the sequence before an element is definetly larger than any number before it, which means that the elements popped when pushing another element needed sorting and belongs to the same chunk. Therefore, by pushing the element one by one into a monotonic stack, we could get the maximum chunk by the size of the stack.

Since it is not very intuitive, belows is an example:

• Input sequence: [1, 0, 2, 3, 4]

1. 1 pushed onto stack.
2. When pushing 0 onto the stack, 1 is popped. ([1, 0] should be in a chunk)
3. 2 pushed onto stack.
4. 3 pushed onto stack.
5. 4 pushed onto stack.

Maximum chunks = 4, splitting into [1, 0], [2], [3], [4].

Monotonic Stack

Reference

A monotonic stack is a stack that has elements monotonically increasing / decreasing. Therefore, for a monotonic increasing stack, if pushing an element smaller then its top element, the stack will need to pop its elements until top is smaller than the element to push to. An example is as follow:

Original stack: [0, 2, 5, 7, 9] pushing element 6
After push operation: [0, 2, 5, 6]

Implementation

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> monoStack;   // monotonic increasing stack
        int largest;

        for (int n: arr) {
            largest = n;
            while (!monoStack.empty() && monoStack.top() > n) {
                largest = max(largest, monoStack.top());
                monoStack.pop();
            }
            monoStack.push(largest);
        }

        return monoStack.size();
    }
};