We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Max Chunks To Make Sorted II

Number: 779

Difficulty: Hard

Paid? No

Companies: Amazon, Apple, Google

Problem Description

Given an integer array arr, the task is to split the array into as many "chunks" (i.e., partitions) as possible such that when each chunk is individually sorted and then concatenated, the resulting array is globally sorted (i.e., equal to the sorted version of arr).

Key Insights

  • The main challenge is to determine valid boundaries to partition the array such that the maximum element in each chunk does not disturb the global order when chunks are sorted individually.
  • A greedy approach can be adopted where for each element, if its value is smaller than the maximum value seen so far, it suggests that elements belong to a previous chunk.
  • A monotonic stack can be used to merge chunks intelligently. When an element is encountered that is smaller than the current chunk’s maximum, you merge (pop) chunks until the stack maintains increasing order.
  • Each element is processed once, ensuring the approach works efficiently for the given constraints.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array since we iterate and possibly merge chunks in a single pass. Space Complexity: O(n) in the worst case for the stack.

Solution

We use a greedy algorithm aided by a monotonic stack. The idea is to iterate through the array and treat each element as a potential start of a new chunk. However, if the current element is smaller than the maximum of the previous chunk, we merge it with that chunk by using the stack. The stack keeps track of the maximum value of each chunk. For every new element, if the stack’s top (last chunk’s maximum) is greater than the element, then merge chunks until the stack is either empty or the top is less than or equal to the element. This ensures that after splitting, sorting each chunk produces a globally sorted array.

Code Solutions

# Python implementation for finding the maximum number of chunks

def max_chunks_to_sorted(arr):
    # Initialize a stack to keep track of maximum values of the chunks
    stack = []
    
    # Iterate over each element in the array
    for num in arr:
        # Set the current value as the new maximum candidate for the current chunk
        current_max = num
        # If the top of the stack (previous chunk max) is greater than the current number,
        # it means the current number should belong in the previous chunk, so merge.
        while stack and stack[-1] > num:
            # Pop the previous chunk's maximum and update the current maximum (simulate merging)
            current_max = max(current_max, stack.pop())
        # Append the updated maximum for the current (or merged) chunk to the stack
        stack.append(current_max)

    # Number of chunks is the size of the stack
    return len(stack)

# Example usage:
arr1 = [5, 4, 3, 2, 1]
print(max_chunks_to_sorted(arr1))  # Output: 1

arr2 = [2, 1, 3, 4, 4]
print(max_chunks_to_sorted(arr2))  # Output: 4
← Back to All Questions