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

Number: 780

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft

Problem Description

Given an array representing a permutation of the integers [0, n-1], split the array into the maximum number of chunks such that when each chunk is sorted individually and then concatenated, the entire array is sorted in ascending order.

Key Insights

  • Since the input is a permutation of 0 through n-1, the correctly sorted array is exactly [0, 1, 2, ..., n-1].
  • While iterating through the array, if the maximum value seen so far is equal to the current index, then all elements up to the current index can form one chunk.
  • A greedy approach by iterating and making a cut whenever max_so_far equals the current index ensures the maximum number of chunks.

Space and Time Complexity

Time Complexity: O(n) - Single pass through the array. Space Complexity: O(1) - Only a few auxiliary variables are used.

Solution

The algorithm uses a greedy approach with a single linear scan of the array. A variable is maintained to track the maximum value seen so far during the iteration. At each index, if the maximum value equals the current index, this indicates that all numbers up to that index are exactly the set {0, 1, ..., i}, thus permitting a chunk division. The process continues until the end of the array, and the count of chunk boundaries is returned as the maximum number of chunks.

Code Solutions

# Define the function
def max_chunks_to_sorted(arr):
    # Initialize count of chunks and the maximum value seen so far
    chunk_count = 0
    max_so_far = 0
    
    # Iterate over the array with index
    for i, num in enumerate(arr):
        # Update the maximum value encountered
        max_so_far = max(max_so_far, num)
        # Check if the current max equals the index
        if max_so_far == i:
            # Valid chunk identified, increment count
            chunk_count += 1
    
    # Return the total number of chunks
    return chunk_count

# Sample test
print(max_chunks_to_sorted([1,0,2,3,4]))  # Expected output: 4
← Back to All Questions