Last updated on January 18th, 2025 at 09:52 pm
Here, we see a Max Chunks To Make Sorted II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Greedy, Two-Pointers
Level of Question
Hard
Max Chunks To Make Sorted II LeetCode Solution
Table of Contents
1. Problem Statement
You are given an integer array arr.
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 = [5,4,3,2,1] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn’t sorted.
Example 2:
Input: arr = [2,1,3,4,4] Output: 4 Explanation: We can split into two chunks, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Monotonic Stack”. This pattern involves using a stack to maintain a sequence of elements in a specific order (e.g., increasing or decreasing) to solve problems related to ranges, intervals, or partitions. The stack helps efficiently manage and process elements while maintaining the desired order.
3. Code Implementation in Different Languages
3.1 Max Chunks To Make Sorted II C++
class Solution {
public:
int maxChunksToSorted(vector& arr) {
int n = arr.size();
vector left_max(n, 0);
left_max[0] = arr[0];
for(int i = 1; i < n; i++)
{
left_max[i] = max(left_max[i - 1], arr[i]);
}
vector right_min(n, 0);
right_min[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
{
right_min[i] = min(right_min[i + 1], arr[i]);
}
int count = 0;
for(int i = 0; i < n - 1; i++)
{
if(left_max[i] <= right_min[i + 1])
{
count++;
}
}
count++;
return count;
}
};
3.2 Max Chunks To Make Sorted II Java
class Solution {
public int maxChunksToSorted(int[] arr) {
Stack<Integer> a= new Stack<Integer>();
for(int i=0;i<arr.length;i++)
{
int mx=arr[i];
while(!a.isEmpty()&&arr[i]<a.peek())
{
mx= Math.max(mx,a.peek());
a.pop();
}
a.push(mx);
}
return(a.size());
}
}
3.3 Max Chunks To Make Sorted II JavaScript
var maxChunksToSorted = function(arr) {
let stack = [arr[0]];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > stack[stack.length - 1]) {
stack.push(arr[i]);
}
else {
let maxElementOfAllChunks = stack[stack.length - 1];
while (arr[i] < stack[stack.length - 1]) {
stack.pop();
}
stack.push(maxElementOfAllChunks);
}
}
return stack.length
};
3.4 Max Chunks To Make Sorted II Python
class Solution(object):
def maxChunksToSorted(self, arr):
stack = []
for num in arr:
m = num
while stack and num < stack[-1]:
m = max(m, stack.pop())
stack.append(m)
return len(stack)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |
- C++ Code uses a two-array approach (
left_maxandright_min) to determine chunk boundaries. - Java, JavaScript, and Python Code use a monotonic stack to dynamically manage chunk boundaries.
- All implementations have the same time complexity (O(n)) and space complexity (O(n)), but the stack-based approach is more space-efficient in practice as it avoids creating two auxiliary arrays.