LeetCode Entry

769. Max Chunks To Make Sorted

19.12.2024 medium 2024 kotlin rust

Maximum independent chunks to merge-sort array

769. Max Chunks To Make Sorted medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/837

Problem TLDR

Maximum independent chunks to merge-sort array #medium

Intuition

Let’s observe when we can split the array:


    // 0 1 2 3 4 5
    // 1 3 4 0 2 5
    // [       ][ ]
    // 1 3 4 0 5 2
    // [         ]
    //

Some observations:

  • all numbers before split border should be less than the current index
  • we should move the border up to the maximum of the seen values

Approach

  • let’s use count
  • the problem size of 10 items hint for some brute-force DFS where we try every possible split and do the sort, however it is not the simplest way of solving

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun maxChunksToSorted(arr: IntArray): Int {
        var max = 0
        return (0..<arr.size).count {
            max = max(max, arr[it])
            it == max
        }
    }



    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let mut m = 0;
        (0..arr.len()).filter(|&i| {
            m = m.max(arr[i]); i as i32 == m
        }).count() as _
    }



    int maxChunksToSorted(vector<int>& arr) {
        int r = 0;
        for (int i = 0, m = 0; i < arr.size(); ++i) {
            m = max(m, arr[i]); if (i == m) r++;
        }
        return r;
    }