769. Max Chunks To Make Sorted

Description

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.

 

Example 1:

Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

 

Constraints:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• All the elements of arr are unique.

Solutions

Solution 1: Greedy + One Pass

Since \(\textit{arr}\) is a permutation of \([0,..,n-1]\), if the maximum value \(\textit{mx}\) among the numbers traversed so far is equal to the current index \(i\), it means a split can be made, and the answer is incremented.

Time complexity is \(O(n)\), and space complexity is \(O(1)\). Where \(n\) is the length of the array \(\textit{arr}\).

Python3JavaC++GoTypeScriptRustC

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        mx = ans = 0
        for i, v in enumerate(arr):
            mx = max(mx, v)
            if i == mx:
                ans += 1
        return ans

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int ans = 0, mx = 0;
        for (int i = 0; i < arr.length; ++i) {
            mx = Math.max(mx, arr[i]);
            if (i == mx) {
                ++ans;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = 0, mx = 0;
        for (int i = 0; i < arr.size(); ++i) {
            mx = max(mx, arr[i]);
            ans += i == mx;
        }
        return ans;
    }
};

func maxChunksToSorted(arr []int) int {
    ans, mx := 0, 0
    for i, v := range arr {
        mx = max(mx, v)
        if i == mx {
            ans++
        }
    }
    return ans
}

function maxChunksToSorted(arr: number[]): number {
    const n = arr.length;
    let ans = 0;
    let mx = 0;
    for (let i = 0; i < n; i++) {
        mx = Math.max(arr[i], mx);
        if (mx == i) {
            ans++;
        }
    }
    return ans;
}

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut mx = 0;
        for i in 0..arr.len() {
            mx = mx.max(arr[i]);
            if mx == (i as i32) {
                ans += 1;
            }
        }
        ans
    }
}

#define max(a, b) (((a) > (b)) ? (a) : (b))

int maxChunksToSorted(int* arr, int arrSize) {
    int ans = 0;
    int mx = -1;
    for (int i = 0; i < arrSize; i++) {
        mx = max(mx, arr[i]);
        if (mx == i) {
            ans++;
        }
    }
    return ans;
}

Solution 2: Monotonic Stack

The solution of method one has certain limitations. If there are duplicate elements in the array, the correct answer cannot be obtained.

According to the problem, we can find that from left to right, each chunk has a maximum value, and these maximum values are monotonically increasing. We can use a stack to store these maximum values of the chunks. The size of the final stack is the maximum number of chunks that can be sorted.

This solution can not only solve this problem but also solve the problem 768. Max Chunks To Make Sorted II. You can try it yourself.

Time complexity is \(O(n)\), and space complexity is \(O(n)\). Where \(n\) is the length of the array \(\textit{arr}\).

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stk = []
        for v in arr:
            if not stk or v >= stk[-1]:
                stk.append(v)
            else:
                mx = stk.pop()
                while stk and stk[-1] > v:
                    stk.pop()
                stk.append(mx)
        return len(stk)

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> stk = new ArrayDeque<>();
        for (int v : arr) {
            if (stk.isEmpty() || v >= stk.peek()) {
                stk.push(v);
            } else {
                int mx = stk.pop();
                while (!stk.isEmpty() && stk.peek() > v) {
                    stk.pop();
                }
                stk.push(mx);
            }
        }
        return stk.size();
    }
}

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> stk;
        for (int v : arr) {
            if (stk.empty() || v >= stk.top()) {
                stk.push(v);
            } else {
                int mx = stk.top();
                stk.pop();
                while (!stk.empty() && stk.top() > v) {
                    stk.pop();
                }
                stk.push(mx);
            }
        }
        return stk.size();
    }
};

func maxChunksToSorted(arr []int) int {
    stk := []int{}
    for _, v := range arr {
        if len(stk) == 0 || v >= stk[len(stk)-1] {
            stk = append(stk, v)
        } else {
            mx := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            for len(stk) > 0 && stk[len(stk)-1] > v {
                stk = stk[:len(stk)-1]
            }
            stk = append(stk, mx)
        }
    }
    return len(stk)
}

function maxChunksToSorted(arr: number[]): number {
    const stk: number[] = [];

    for (const x of arr) {
        if (stk.at(-1)! > x) {
            const top = stk.pop()!;
            while (stk.length && stk.at(-1)! > x) stk.pop();
            stk.push(top);
        } else stk.push(x);
    }

    return stk.length;
}

function maxChunksToSorted(arr) {
    const stk = [];

    for (const x of arr) {
        if (stk.at(-1) > x) {
            const top = stk.pop();
            while (stk.length && stk.at(-1) > x) stk.pop();
            stk.push(top);
        } else stk.push(x);
    }

    return stk.length;
}

Comments