768. Max Chunks To Make Sorted II

HardStackGreedyArraySortingMonotonic Stack
Leetcode Link

Problem Description

The given LeetCode problem focuses on an array partitioning and sorting strategy. The objective is to split the input integer array arr into contiguous chunks, sort each chunk individually, and then concatenate the chunks together. The goal is for the concatenated result to produce the same sequence as sorting the entire original array at once. The task is to determine the maximum number of such chunks we can create. A successful solution to this problem would allow us to find the most efficient way to break down an array into independently sortable pieces that, when combined, yield a fully sorted array.

Intuition

The intuition behind the solution lies in leveraging the idea of a monotonically increasing stack to determine the number of chunks. Since each chunk, once sorted, should be a part of the completely sorted array, we can track the maximum element of the current chunk we are forming. Each element in the stack represents the maximum of a chunk.

As we iterate through the array arr, we examine each element. If the current element is greater than or equal to the element at the top of the stack (which means it is greater than all elements in the current chunk), it can form a new chunk or be a part of the current chunk without breaking the sorting order after concatenation.

However, if the current element is smaller than the top of the stack, it belongs to one of the previous chunks. This is where we start popping from the stack while the top of the stack is greater than the current element, effectively merging those chunks. Once we finished popping from the stack (have found a chunk where the current element could fit), we push the maximum of the last popped chunk (the largest element before the merge) back onto the stack, ensuring that the sorting condition holds true for the updated chunk.

The number of elements left in the stack at the end of this process corresponds to the maximum number of chunks we can make since each stack element represents the max value of the individual sorted chunks.

Learn more about Stack, Greedy, Sorting and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The solution makes use of a stack data structure to help track the largest number we can form within a chunk. Here's a step-by-step explanation of how the implementation tackles the problem:

  1. We initialize an empty list stk that we will use as our stack. The stack is used to maintain the maximum elements of the chunks we form as we iterate through the array.

  2. As we iterate over each value v in arr, we have two conditions to consider: a. If the stack is empty or the current value v is greater than or equal to the maximum value at the top of the stack (stk[-1]), we can push v onto the stack. This signifies either the start of a new chunk or that v can be a part of the current chunk without disrupting the sorted order when concatenated.

    b. If the current value v is less than the maximum value at the top of the stack, this indicates that v belongs to a previous chunk, and we need to merge some chunks to maintain the sorted order upon concatenation. We pop values from the stack until we find a value that is not greater than v. During this process, we keep track of the maximum value that we pop by assigning it to mx. This ensures that despite merging, the maximum value maintains its position to preserve the sorting requirement.

  3. After the popping condition ends, we push the value mx back onto the stack. Now, mx represents the maximum value of the newly formed merged chunk.

  4. Once we have finished iterating through the array, the stack will contain a certain number of elements. Each element corresponds to a chunk with its maximum value. Therefore, the length of the final stack represents the maximum number of chunks we are able to make such that when these chunks are sorted individually and concatenated, they form a sorted list equivalent to sorting the entire arr.

  5. The function returns len(stk), the number of individual chunks that can be created.

This approach effectively takes advantage of the stack data structure to dynamically manage the chunks during the array traversal, merging chunks as necessary to ensure that the final concatenation of sorted chunks results in a list sorted in non-decreasing order.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we have the following array arr: [2, 4, 1, 6, 5, 9, 7].

Here's how the solution algorithm would process this array:

  1. Initialize an empty stack stk.
  2. Iterate over the array arr. Position 0: v = 2. Stack is empty, so push v onto the stack. Stack now: [2].
  3. Position 1: v = 4. It's greater than the top of the stack, so push v onto the stack. Stack now: [2, 4].
  4. Position 2: v = 1. It's smaller than the top of the stack. Start popping from the stack until the top is not greater than v. We pop 4 and 2 from the stack, and the maximum value mx of popped elements is 4. Stack is empty now, push the mx back. Stack now: [4].
  5. Position 3: v = 6. It's greater than the top of the stack, so push v onto the stack. Stack now: [4, 6].
  6. Position 4: v = 5. It's smaller than the top of the stack. Start popping from the stack. Pop 6 and 4. The new mx is 6. The stack is empty, so we push mx back. Stack now: [6].
  7. Position 5: v = 9. It's greater than the top of the stack, so push v onto the stack. Stack now: [6, 9].
  8. Position 6: v = 7. It's smaller than the top of the stack. Start popping from the stack. Pop 9, the new mx is 9. Push mx back onto the stack. Stack now: [9].
  9. Finish iterating over the array. The stack has executed multiple merges and now it has one element, which represents the number of chunks.

Each pass through the array adjusted the individual chunks in a way that they could be merged back together into a fully sorted array. At the end of this process, the stack size (which is now 1) represents the maximum number of chunks that when sorted individually and concatenated form the sorted array.

Hence, for the given example array, the maximum number of chunks that we can form is 1.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxChunksToSorted(self, arr: List[int]) -> int:
5        # Initialize an empty stack to keep track of the current maximum in each chunk
6        stack = []
7      
8        # Iterate through each value in the array
9        for value in arr:
10            # If the stack is empty or the current value is greater than or equal
11            # to the top of the stack, this value can start a new chunk.
12            if not stack or value >= stack[-1]:
13                stack.append(value)
14            else:
15                # If the current value is smaller than the top of the stack, we need
16                # to merge this value into the previous chunk. So we remove elements
17                # from the stack until we find a value smaller than the current one.
18                # This ensures all earlier elements are part of a sorted subarray.
19                max_in_chunk = stack.pop()
20                while stack and stack[-1] > value:
21                    stack.pop()
22              
23                # After merging, we push the maximum value of the merged chunk back onto
24                # the stack. This represents the maximum value of the new chunk after merging.
25                stack.append(max_in_chunk)
26      
27        # The length of the stack represents the number of chunks since each stack element
28        # corresponds to the maximum value of a sorted chunk.
29        return len(stack)
30
1class Solution {
2    public int maxChunksToSorted(int[] arr) {
3        Deque<Integer> stack = new ArrayDeque<>(); // Use a deque as a stack to store values
4
5        for (int value : arr) { // Iterate through each value in the array
6            if (stack.isEmpty() || stack.peek() <= value) { // If stack is empty or the top is less than or equal to current value
7                stack.push(value); // Push the current value onto the stack
8            } else {
9                // If the current value is less, this means a new chunk must be formed
10                int maxInChunk = stack.pop(); // Pop the top value, which is the maximum in the current chunk
11                // Pop all values in the chunk which are greater than current value
12                while (!stack.isEmpty() && stack.peek() > value) {
13                    stack.pop();
14                }
15                // Push the max value back to represent the current chunk
16                stack.push(maxInChunk);
17            }
18        }
19
20        return stack.size(); // The number of chunks is the size of the stack
21    }
22}
23
1#include<vector>
2#include<stack>
3using namespace std;
4
5class Solution {
6public:
7    int maxChunksToSorted(vector<int>& arr) {
8        stack<int> valueStack; // Use a stack to store values
9
10        // Iterate over each element in the array
11        for (int value : arr) {
12            // If the stack is empty or the current value is greater than or equal
13            // to the top of the stack, push the current value onto the stack.
14            if (valueStack.empty() || valueStack.top() <= value) {
15                valueStack.push(value);
16            } else {
17                // If the current value is less than the top of the stack,
18                // then we need to merge the current chunk with the previous chunks
19                // until the value at the top of the stack is no longer greater
20                // than the current value.
21
22                // Store the maximum value in the current chunk
23                int maxValueInChunk = valueStack.top();
24                valueStack.pop(); // Remove the top element as we're going to merge chunks
25
26                // Keep removing elements from the stack until the top is not greater
27                // than the current value.
28                while (!valueStack.empty() && valueStack.top() > value) {
29                    valueStack.pop();
30                }
31
32                // Push the maximum value of the merged chunks back onto the stack
33                // because it represents the maximum value up to the current point,
34                // and chunks need to be sorted independently.
35                valueStack.push(maxValueInChunk);
36            }
37        }
38
39        // The size of the stack represents the maximum number of chunks that are sorted
40        // when taken independently. Hence, we can return the stack size directly.
41        return valueStack.size();
42    }
43};
44
1function maxChunksToSorted(arr: number[]): number {
2    // Initialize an empty stack to keep track of the max value of each chunk
3    const stack: number[] = [];
4
5    // Iterate through each number in the input array
6    for (const num of arr) {
7        // If the current number is smaller than the last number on the stack,
8        // we need to merge the current chunk with the previous one.
9        if (stack.length > 0 && num < stack[stack.length - 1]) {
10            // The current chunk's max value is stored.
11            const currentMax = stack.pop();
12
13            // Keep removing elements from the stack until we find a value
14            // not greater than the current number to ensure chunks are sorted.
15            while (stack.length > 0 && num < stack[stack.length - 1]) {
16                stack.pop();
17            }
18
19            // Push the max value of the merged chunk back onto the stack.
20            stack.push(currentMax);
21        } else {
22            // As the current number is not smaller than the last chunk's max,
23            // push the number onto the stack to start a new chunk.
24            stack.push(num);
25        }
26    }
27
28    // The number of chunks is the stack's length after merging.
29    return stack.length;
30}
31
Not Sure What to Study? Take the 2-min Quiz๏ผš

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

The given code snippet is designed to solve the problem of finding the maximum number of chunks in which an array can be split such that when the individual chunks are sorted, the entire array is sorted. This is achieved by maintaining a stack, stk, and iterating over the elements of the array, arr.

Time Complexity

The time complexity of the code is O(n). This is because there is a single for-loop iterating over the elements of the array arr. Although there is a while-loop inside the for-loop, each element from the array is pushed onto the stack at most once and popped from the stack at most once. This means that even with the inner while-loop, each operation on an element (either push or pop) is done only a constant number of times. Overall, the number of operations is proportional to the number of elements n.

Space Complexity

The space complexity of the code is O(n). In the worst case, the stack stk could potentially store all the elements of the array if the array is in ascending order. As a result, the amount of space used is proportional to the number of elements in the input array, n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Recommended Readings

Stack Intro

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

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

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

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.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ