Leetcode 769. Max Chunks To Make Sorted

Problem Explanation

Given is an array 'arr' that is a permutation of [0, 1, ..., arr.length - 1]. The task is to split the array into several chunks (partitions), then sort each chunk individually. Once we get these sorted chunks, we concatenate them together to form a complete array. The given problem demands the state of maximum possible chunks that we can make such that, after sorting these chunks individually and then merging them, we get a sorted array.

Approach to the Solution

In this problem, the main approach to get the maximum number of chunks is to compare the current maximum in the array ‘arr’ with the current index i.

So the steps for the approach are:

1. Initialize an answer variable ‘ans’ to keep the count of maximum chunks and a variable ‘maxi’ with INT_MIN to keep track of the maximum till now.

   ans = 0

   maxi = INT_MIN

2. Loop through the array 'arr', find the maximum till now, and compare it with the current index.

   • If the maximum value equals the current index, increment the value of 'ans' by 1 because it implies that all elements before 'i' (including 'i') are less than or equal to 'i' and it forms a chunk.

The solution works based on a simple intuition, that for every index 'i', if the maximum value till this index equals this index, we could make a chunk divide at this index.

Example

Let's understand this with an example:

arr = [1, 0, 2, 3, 4]

1. arr[0]: the maximum so far is 1 (maxi=1), which is not equal to the current index (i=0).

2. arr[1]: the maximum so far is still 1 (maxi=1), and it equals the current index (i=1). So, increment 'ans'.

3. arr[2], arr[3] and arr[4]: for these elements, the maximum so far (2,3, and 4 respectively) equals the current index (2,3 and 4). So, increment 'ans' for each.

Finally, this gives 'ans' = 4.

Solution

Python

1
2python
3class Solution(object):
4    def maxChunksToSorted(self, arr):
5        maxi = float('-inf') # Initialize maximum number with 0 at starting
6        ans = 0 # Initialize final answer to 0 which will contain count of chunks
7
8        for i in range(len(arr)): # for each index in given list
9            maxi = max(maxi, arr[i]) # get maximum number till index i
10            if maxi == i: # check for above condition, if true increment ans
11                ans += 1
12
13        return ans

Java

1
2java
3class Solution {
4    public int maxChunksToSorted(int[] arr) {
5        int ans = 0, maxi = Integer.MIN_VALUE;
6
7        for (int i = 0; i < arr.length; ++i) {
8            maxi = Math.max(maxi, arr[i]);
9            if (maxi == i)
10                ++ans;
11        }
12
13        return ans;
14    }
15}

JavaScript

1
2javascript
3var maxChunksToSorted = function(arr) {
4    let maxi = Number.MIN_SAFE_INTEGER, ans = 0;
5
6    for(let i = 0; i < arr.length; i++) {
7        maxi = Math.max(maxi, arr[i]);
8        if(maxi == i) 
9            ans++;
10    }
11
12    return ans;
13};

C#

1
2csharp
3public class Solution {
4    public int MaxChunksToSorted(int[] arr) {
5        int maxi = int.MinValue, ans = 0;
6
7        for(int i = 0; i < arr.Length; i++){
8            maxi = Math.Max(maxi, arr[i]);
9            if(maxi == i)
10                ans++;
11        }
12
13        return ans;
14    }
15}

C++

1
2cpp
3class Solution {
4public:
5    int maxChunksToSorted(vector<int>& arr) {
6        int ans = 0, maxi = INT_MIN;   //initializing answer=0 and maxi as minimum integer
7
8        for (int i = 0; i < arr.size(); ++i) {
9            maxi = max(maxi, arr[i]);  // finding out the maximum value in the array til ith index
10            if (maxi == i)     
11                ++ans;   // if ith index is equal to maximum value than we increase our answer by 1
12        }
13
14        return ans;   // returning final answer
15    }
16};

Go

1
2go
3import "math"
4
5func maxChunksToSorted(arr []int) int {
6    maxi := math.MinInt32
7    ans := 0
8
9    for i := 0; i < len(arr); i++ {
10        if arr[i] > maxi {
11            maxi = arr[i]
12        }
13        if maxi == i {
14            ans++
15        }
16    }
17
18    return ans
19}

R

1
2r
3maxChunksToSorted <- function(arr) {
4    maxi = -Inf
5    ans = 0
6    for (i in 1:length(arr)) {
7        maxi = max(maxi, arr[i])
8        if (maxi == (i-1)) {
9            ans = ans + 1
10        }
11    }
12    return (ans)
13}

Haskell

1
2haskell
3import Data.List
4
5maxChunksToSorted :: [Int] -> Int 
6maxChunksToSorted arr = let process (maxi, ans) (idx,val) = let maxi' = max maxi val
7                                                                    ans'  = if maxi' == idx then ans + 1 else ans
8                                                                in  (maxi', ans') 
9                        in  snd $ foldl' process (-1,0) $ zip [0..] arr

Ruby

1
2ruby
3class Solution
4    def max_chunks_to_sorted(arr)
5        maxi = -Float::INFINITY
6        ans = 0
7        arr.each_with_index do |num, i|
8            maxi = [maxi, num].max
9            ans += 1 if maxi == i
10        end
11        ans
12    end
13end

In all of these languages, we followed the similar approach of comparing the maximum so far with the current index through an iterative loop. The results differed per language depending on the specific syntax and style variations, but the core logic remained the same.