Jobs

Interviews

Discussions

Max Chunks To Make Sorted II

Hard

Google

1 view

Topics:

Arrays

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.

For example:

arr = [5,4,3,2,1]

The correct output is 1 because 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.

Another example is:

arr = [2,1,3,4,4]

Return 4 because 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.

How would you approach solving this problem?

Max Chunks To Make Sorted II

Hard

Google

1 view

Topics:

Arrays

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.

For example:

arr = [5,4,3,2,1]

Another example is:

arr = [2,1,3,4,4]

Return 4 because 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.

How would you approach solving this problem?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the input array contain negative numbers or zeros?
Are there duplicate numbers in the input array, and if so, how should they be handled when determining chunks?
If the array is already sorted, should I return the array size as the number of chunks?
Are all the numbers integers, or could there be floating-point values?

Brute Force Solution

Approach

The brute force approach to solving this chunking problem is to consider every possible way to split the given list into chunks. Then, we check if, after sorting each of the chunks individually, combining them results in a fully sorted list.

Here's how the algorithm would work step-by-step:

First, imagine there's only one big chunk that contains the entire original list.
Next, consider splitting the list into two chunks by making every possible cut.
Then, think about splitting the list into three chunks, again exploring all possible ways to make those two cuts.
Continue doing this for every possible number of chunks, up to the number of items in the list.
For each possible way you split the list into chunks, sort each chunk individually.
After sorting each chunk, put the chunks back together in the order they were originally arranged.
See if the resulting list is completely sorted from smallest to largest.
If the resulting list is sorted, that's a valid chunking.
Keep track of how many chunks were in each valid chunking.
Finally, the largest number of chunks among all the valid chunkings is the answer.

Code Implementation

def max_chunks_to_sorted_brute_force(arr): 
    array_length = len(arr)
    max_chunks = 0

    for number_of_chunks in range(1, array_length + 1):
        # Iterate through possible chunk combinations
        for i in range(1 << (array_length - 1)): 
            if bin(i).count('1') != number_of_chunks - 1:
                continue

            chunks = []
            start_index = 0
            current_chunk = []

            for index in range(array_length - 1):
                current_chunk.append(arr[index])
                # Splitting point, create a new chunk
                if (i >> index) & 1:
                    chunks.append(current_chunk)
                    current_chunk = []
                    start_index = index + 1

            current_chunk.append(arr[array_length - 1])
            chunks.append(current_chunk)

            sorted_chunks = [sorted(chunk) for chunk in chunks]
            merged_array = []

            for chunk in sorted_chunks:
                merged_array.extend(chunk)

            is_sorted = all(merged_array[index] <= merged_array[index + 1] for index in range(array_length - 1))

            # Check if the merged array is sorted
            if is_sorted:
                # Track the maximum number of chunks
                max_chunks = max(max_chunks, number_of_chunks)

    return max_chunks

Big(O) Analysis

Time Complexity

O(n! * n log n) – The algorithm considers all possible chunk combinations, which can be represented as partitions of the input array. The number of such partitions grows faster than exponentially but is bounded above by n!. For each potential chunking, each chunk must be sorted individually, requiring O(n log n) time in the worst case if we assume we use an efficient sorting algorithm like merge sort. Since we have at most n chunks, this contributes a factor of O(n * n log n). Multiplying the number of possible chunkings by the sorting cost for each one yields a final time complexity of O(n! * n log n).

Space Complexity

O(N) – The brute force approach described involves creating multiple chunks, sorting each chunk, and then concatenating them. Sorting each chunk requires a temporary space proportional to the size of the chunk, and in the worst-case scenario, we might need to store the entire input array in a temporary sorted form. Additionally, concatenating the sorted chunks creates a new list which, in the worst case, has a size equal to the original input list. Therefore, the auxiliary space used is proportional to the input size N, leading to a space complexity of O(N).

Optimal Solution

Approach

The key idea is to determine how many independent blocks we can split the input into, such that sorting each block individually results in the entire array being sorted. We can efficiently determine these block boundaries by tracking the maximum value seen so far from the left and the minimum value seen so far from the right.

Here's how the algorithm would work step-by-step:

Create two containers. One will hold the maximum value seen so far from the left side, and the other will hold the minimum value seen so far from the right side.
Calculate the maximum from the left. For each position, store the maximum value encountered up to that point.
Calculate the minimum from the right. For each position, store the minimum value encountered from that position to the end.
Now, compare the maximum from the left with the minimum from the right. If at any position, the maximum value seen so far from the left is less than or equal to the minimum value seen so far from the right (starting from the next position), it means we can split the array into two chunks at that position.
Count the number of such positions where the split is possible. This count represents the maximum number of chunks we can have.

Code Implementation

def maxChunksToSorted(array):
    array_length = len(array)

    maximum_from_left = [0] * array_length
    minimum_from_right = [0] * array_length

    maximum_from_left[0] = array[0]
    for i in range(1, array_length): 
        maximum_from_left[i] = max(maximum_from_left[i - 1], array[i])

    minimum_from_right[array_length - 1] = array[array_length - 1]
    for i in range(array_length - 2, -1, -1): 
        minimum_from_right[i] = min(minimum_from_right[i + 1], array[i])

    number_of_chunks = 1

    # Count chunks based on max left vs min right
    for i in range(array_length - 1): 
        # Crucial check to see if a split is possible
        if maximum_from_left[i] <= minimum_from_right[i + 1]:
            number_of_chunks += 1

    return number_of_chunks

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves iterating through the input array of size n three times. The first pass calculates the maximum from the left in O(n) time. The second pass calculates the minimum from the right, also in O(n) time. Finally, the third pass compares the maximum from the left and the minimum from the right to determine chunk boundaries, which takes O(n) time. Therefore, the total time complexity is O(n) + O(n) + O(n) = O(3n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses two additional arrays, max_from_left and min_from_right, to store the maximum value seen so far from the left and the minimum value seen so far from the right, respectively. Both of these arrays have a size equal to the input array's size, N. Therefore, the auxiliary space used is directly proportional to the input size, N. This results in a linear space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as an empty array is already sorted and requires no chunks.
Array with a single element	Return 1, since a single element array is already sorted and requires one chunk.
Array with all identical elements	The prefix maximum will always be less than or equal to the overall minimum to the right, resulting in a single chunk (return 1).
Array is already sorted in ascending order	The prefix maximum will always be less than or equal to the overall minimum to the right, resulting in n chunks (return the length of array).
Array is sorted in descending order	Each element will require its own chunk until the end of the array, resulting in 1 chunk.
Array with large numbers causing potential integer overflow when calculating prefix maximum or right minimum	Use long data type to store prefix maximum and right minimum to prevent integer overflow.
Large input array causing memory constraints	The solution uses O(n) space for prefix maximum and right minimum, consider using techniques like divide and conquer if memory is severely limited.
Array containing negative and positive numbers	The algorithm correctly handles negative and positive numbers as the prefix maximum and right minimum are calculated correctly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array?
Can the input array contain negative numbers or zeros?
Are there duplicate numbers in the input array, and if so, how should they be handled when determining chunks?
If the array is already sorted, should I return the array size as the number of chunks?
Are all the numbers integers, or could there be floating-point values?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine there's only one big chunk that contains the entire original list.
Next, consider splitting the list into two chunks by making every possible cut.
Then, think about splitting the list into three chunks, again exploring all possible ways to make those two cuts.
Continue doing this for every possible number of chunks, up to the number of items in the list.
For each possible way you split the list into chunks, sort each chunk individually.
After sorting each chunk, put the chunks back together in the order they were originally arranged.
See if the resulting list is completely sorted from smallest to largest.
If the resulting list is sorted, that's a valid chunking.
Keep track of how many chunks were in each valid chunking.
Finally, the largest number of chunks among all the valid chunkings is the answer.

Code Implementation

def max_chunks_to_sorted_brute_force(arr): 
    array_length = len(arr)
    max_chunks = 0

    for number_of_chunks in range(1, array_length + 1):
        # Iterate through possible chunk combinations
        for i in range(1 << (array_length - 1)): 
            if bin(i).count('1') != number_of_chunks - 1:
                continue

            chunks = []
            start_index = 0
            current_chunk = []

            for index in range(array_length - 1):
                current_chunk.append(arr[index])
                # Splitting point, create a new chunk
                if (i >> index) & 1:
                    chunks.append(current_chunk)
                    current_chunk = []
                    start_index = index + 1

            current_chunk.append(arr[array_length - 1])
            chunks.append(current_chunk)

            sorted_chunks = [sorted(chunk) for chunk in chunks]
            merged_array = []

            for chunk in sorted_chunks:
                merged_array.extend(chunk)

            is_sorted = all(merged_array[index] <= merged_array[index + 1] for index in range(array_length - 1))

            # Check if the merged array is sorted
            if is_sorted:
                # Track the maximum number of chunks
                max_chunks = max(max_chunks, number_of_chunks)

    return max_chunks

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create two containers. One will hold the maximum value seen so far from the left side, and the other will hold the minimum value seen so far from the right side.
Calculate the maximum from the left. For each position, store the maximum value encountered up to that point.
Calculate the minimum from the right. For each position, store the minimum value encountered from that position to the end.
Now, compare the maximum from the left with the minimum from the right. If at any position, the maximum value seen so far from the left is less than or equal to the minimum value seen so far from the right (starting from the next position), it means we can split the array into two chunks at that position.
Count the number of such positions where the split is possible. This count represents the maximum number of chunks we can have.

Code Implementation

def maxChunksToSorted(array):
    array_length = len(array)

    maximum_from_left = [0] * array_length
    minimum_from_right = [0] * array_length

    maximum_from_left[0] = array[0]
    for i in range(1, array_length): 
        maximum_from_left[i] = max(maximum_from_left[i - 1], array[i])

    minimum_from_right[array_length - 1] = array[array_length - 1]
    for i in range(array_length - 2, -1, -1): 
        minimum_from_right[i] = min(minimum_from_right[i + 1], array[i])

    number_of_chunks = 1

    # Count chunks based on max left vs min right
    for i in range(array_length - 1): 
        # Crucial check to see if a split is possible
        if maximum_from_left[i] <= minimum_from_right[i + 1]:
            number_of_chunks += 1

    return number_of_chunks

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as an empty array is already sorted and requires no chunks.
Array with a single element	Return 1, since a single element array is already sorted and requires one chunk.
Array with all identical elements	The prefix maximum will always be less than or equal to the overall minimum to the right, resulting in a single chunk (return 1).
Array is already sorted in ascending order	The prefix maximum will always be less than or equal to the overall minimum to the right, resulting in n chunks (return the length of array).
Array is sorted in descending order	Each element will require its own chunk until the end of the array, resulting in 1 chunk.
Array with large numbers causing potential integer overflow when calculating prefix maximum or right minimum	Use long data type to store prefix maximum and right minimum to prevent integer overflow.
Large input array causing memory constraints	The solution uses O(n) space for prefix maximum and right minimum, consider using techniques like divide and conquer if memory is severely limited.
Array containing negative and positive numbers	The algorithm correctly handles negative and positive numbers as the prefix maximum and right minimum are calculated correctly.