769. Max Chunks To Make Sorted
Problem Description
You are given an integer array called arr
, which contains n
elements. Each element in the array is unique and ranges from 0 to n - 1
, essentially representing a permutation of these numbers. The goal is to divide this array into several non-overlapping "chunks" (subarrays), sort each of these chunks individually, and then concatenate them back together to form a single sorted array. The task is to find the maximum number of chunks that can be made such that when they are sorted individually and then concatenated, the result is a sorted version of the original array.
Intuition
The intuition behind the solution is based on the property of permutations and how the original array can be split into the maximum number of chunks. Since the array is a permutation of numbers from 0 to n - 1
, if all the chunks are individually sorted, then regardless of where the chunks are split, the concatenated chunks will produce a sorted array. To maximize the number of chunks, we need to exploit the fact that if the maximum value in a chunk is equal to its last index, then this chunk can be independently sorted without affecting the sorting of the entire array.
For example, consider we are at index i
in the array, and the maximum value encountered so far is mx
. If i
and mx
are equal, it means all numbers from 0 to i
are included in this chunk, so this chunk can be independently sorted. We increment our chunk count (ans
) everytime such a condition occurs. The process is repeated as we iterate through the array, resulting in ans
incrementing each time a self-contained chunk (where its maximum value matches its last index) is found. This logic ensures we are splitting the array into the largest possible number of valid chunks that, when sorted individually, will form the overall sorted array.
This approach's correctness lies in the fact that for every chunk ending at index i
, if the maximum value in that chunk is also i
, sorting that chunk will simply place all elements from 0 to i
(which are already within the chunk) in their correct sorted position. No other elements outside this chunk are affected, guaranteeing that each such chunk contributes to the overall sorted array.
Learn more about Stack, Greedy, Sorting and Monotonic Stack patterns.
Solution Approach
The impementation of the solution is straightforward. The steps can be broken down as follows:
-
We initialize two variables,
mx
andans
.mx
will keep track of the maximum value encountered so far as we iterate through the array, andans
will count the number of chunks. -
We use a
for
loop to iterate through each element represented byi
and its valuev
in thearr
. -
For every element
v
in the array, we updatemx
to be the maximum ofmx
andv
, using the expressionmax(mx, v)
. This ensures thatmx
reflects the highest number among all the elements we've encountered up to the current position. -
We check if the current index
i
is equal to the maximum valuemx
we've found so far. If it is, it means we've found a valid chunk — all integers from 0 up to the current indexi
must be contained within this chunk, as the permutation contains every integer from 0 ton - 1
exactly once. Therefore, we can independently sort this chunk without affecting the overall sorting of the array. When such a condition is met, we increment theans
by 1, indicating we can form one more chunk. -
We continue this process for all elements in the
arr
. -
After the loop completes,
ans
contains the largest number of chunks we can form such that individually sorting these chunks and then concatenating them results in a sorted array.
No additional data structures are needed, and the pattern used is simple iteration with a check for the current index against the current maximum value. This is an efficient solution as it achieves the task with a time complexity of O(n) where n is the length of arr
, as it requires only a single pass through the array. The space complexity is also O(1) since we're not using any additional storage that scales with the input size.
Here is the implemented function:
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
This function takes the arr
as input and returns the maximum number of chunks ans
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example array arr
: [1, 0, 2, 4, 3]
-
Initially, we set
mx
andans
to 0.mx
will track the maximum number we encounter, andans
will count the chunks. -
We begin iterating through
arr
with afor
loop:- At i = 0, v = arr[0] = 1; we update
mx = max(0, 1)
somx
becomes 1. Sincei
is not equal tomx
, we do not incrementans
. - At i = 1, v = arr[1] = 0; we update
mx = max(1, 0)
somx
stays 1. Now,i
is equal tomx
, which means all numbers from 0 to 1 are within this chunk. We incrementans
to 1. - At i = 2, v = arr[2] = 2; we update
mx = max(1, 2)
somx
becomes 2. Again,i
equalsmx
, indicating another chunk. We incrementans
to 2. - At i = 3, v = arr[3] = 4; we update
mx = max(2, 4)
somx
becomes 4.i
is not equal tomx
, we do not incrementans
. - At i = 4, v = arr[4] = 3; we update
mx = max(4, 3)
somx
stays 4. Now,i
equalsmx
, indicating another valid chunk. We incrementans
to 3.
- At i = 0, v = arr[0] = 1; we update
-
Having completed the loop, we find that the array can be split into a maximum of
3
chunks:[1, 0]
,[2]
, and[4, 3]
. When we sort these subarrays independently and then concatenate them, we get the sorted array:[0, 1, 2, 3, 4]
.
The final answer ans
is 3, which signifies there are 3 chunks that can be individually sorted to result in a fully sorted array. This is confirmed by our walkthrough with the example array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxChunksToSorted(self, arr: List[int]) -> int:
5 # Initialize the maximum value found so far and the answer counter
6 max_value = 0
7 chunks_count = 0
8
9 # Enumerate over the array to get both index and value
10 for index, value in enumerate(arr):
11 # Update the maximum value found in the array thus far
12 max_value = max(max_value, value)
13
14 # If the current index equals the maximum value encountered,
15 # it means we can form a chunk that, when sorted independently,
16 # would still maintain the overall order when merged with adjacent chunks.
17 if index == max_value:
18 # Thus, we increase the chunks count by 1
19 chunks_count += 1
20
21 # Return the total number of chunks we can split the array into
22 return chunks_count
23
1class Solution {
2 public int maxChunksToSorted(int[] arr) {
3 int chunkCount = 0; // Initialize the count of chunks
4 int maxSoFar = 0; // Initialize the maximum value found so far in the array
5
6 // Iterate through the array
7 for (int index = 0; index < arr.length; ++index) {
8 // Update the maximum value seen so far
9 maxSoFar = Math.max(maxSoFar, arr[index]);
10
11 // If the current index is equal to the maximum value encountered,
12 // it means all values before this index are smaller or equal to 'index'
13 // and this position is a valid chunk boundary
14 if (index == maxSoFar) {
15 // Increment the count of chunks
16 ++chunkCount;
17 }
18 }
19
20 return chunkCount; // Return the total number of chunks
21 }
22}
23
1#include <vector>
2#include <algorithm> // For use of the max function
3
4class Solution {
5public:
6 int maxChunksToSorted(vector<int>& arr) {
7 int chunkCount = 0; // Variable to count chunks
8 int maxElement = 0; // Variable to store the maximum element found so far
9
10 // Iterate through the vector elements
11 for (int index = 0; index < arr.size(); ++index) {
12 maxElement = std::max(maxElement, arr[index]); // Update maxElement with the highest between maxElement and the current element
13
14 // If the maximum element we've found so far is equal to the index,
15 // it means all previous elements are ≤ index and can form a chunk
16 if (index == maxElement) {
17 ++chunkCount; // Increment the chunk count as we can make a new chunk
18 }
19 }
20
21 return chunkCount; // Return the total number of chunks
22 }
23};
24
1// Function to determine the maximum number of chunks that the array can be
2// split into so that after sorting each chunk individually and then concatenating
3// them back in order, the resultant array is sorted.
4function maxChunksToSorted(arr: number[]): number {
5 const n: number = arr.length; // The length of the input array.
6 let answer: number = 0; // The number of chunks that the input array can be split into.
7 let currentMax: number = 0; // The maximum value found so far in the array up to the current index.
8
9 // Iterate through the array to find chunks.
10 for (let i: number = 0; i < n; i++) {
11 // Update the current maximum value found.
12 currentMax = Math.max(arr[i], currentMax);
13
14 // If the current maximum is equal to the index, a sorted chunk is found.
15 // This is based on the property that in a sorted array of distinct numbers ranging from 0 to n-1,
16 // the number at index i should be i itself, if the chunks before are correctly placed.
17 if (currentMax === i) {
18 answer++; // Increment the answer as we can split here.
19 }
20 }
21 // Return the number of sorted chunks possible.
22 return answer;
23}
24
Time and Space Complexity
The given code snippet is designed to find the maximum number of chunks a given array can be divided into so that, when each chunk is sorted individually, the entire array is sorted.
Time Complexity:
The time complexity of the function is determined by the for loop iterating over each element of the array. Since there is only one loop in the function that goes through the array of n
elements once, the time complexity is O(n
), where n
is the size of the array.
Space Complexity:
The space complexity is determined by the amount of additional memory used by the algorithm. Here, only a fixed number of variables mx
and ans
are used regardless of the input size, which means the space complexity is O(1
) as they use constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Don’t Miss This!