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:
-
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
-
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]
-
arr[0]: the maximum so far is 1 (maxi=1), which is not equal to the current index (i=0).
-
arr[1]: the maximum so far is still 1 (maxi=1), and it equals the current index (i=1). So, increment 'ans'.
-
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.