Max Chunks To Make Sorted II - Practice Coding Problems

Max Chunks To Make Sorted II - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: arr = [5,4,3,2,1]

› Output: 1

💡 Note: The array is already in reverse order. No matter how we split it, we need all elements together to form the sorted sequence [1,2,3,4,5]. Only 1 chunk is possible.

Example 2 — Multiple Chunks Possible

$ Input: arr = [2,1,3,4,4]

› Output: 4

💡 Note: We can split as [2,1] | [3] | [4] | [4]. After sorting each chunk: [1,2] + [3] + [4] + [4] = [1,2,3,4,4], which matches the sorted array.

Example 3 — Already Sorted

$ Input: arr = [1,2,3,4,5]

› Output: 5

💡 Note: Array is already sorted, so we can make each element its own chunk: [1] | [2] | [3] | [4] | [5]. Maximum possible chunks.

Constraints

1 ≤ arr.length ≤ 2000
0 ≤ arr[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array that needs to be partitioned

Find Partitions

Identify positions where we can safely split the array

Sort and Verify

Each chunk sorts to correct position in final array

Key Takeaway

🎯 Key Insight: We can safely split after position i if all elements in positions 0 to i belong to the first i+1 positions in the sorted array

Asked in

G Google 42 a Amazon 28 f Facebook 15 M Microsoft 12

The key insight is that we can make a cut after position i if the maximum element in positions 0 to i equals the (i+1)th smallest element overall. The monotonic stack approach is optimal with O(n) time and elegantly handles merging chunks when smaller elements appear. Alternative greedy approach takes O(n log n) but is simpler to understand.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach with Prefix Analysis	O(n log n)	O(n)	Count positions where all elements seen so far can be correctly placed
Monotonic Stack Approach	O(n)	O(n)	Use a stack to track chunk maximums and merge chunks when necessary
Brute Force - Try All Partitions	O(2ⁿ × n log n)	O(n)	Generate all possible ways to partition the array and check which ones work

Greedy Approach with Prefix Analysis — Algorithm Steps

Sort the array to know the target order
Track running maximum as we scan the array
Compare with expected maximum at each position
Count valid cut positions
Add one more chunk for the final segment

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Maximum

Keep running maximum of elements seen so far

Compare with Sorted

Check if current max equals expected value in sorted array

Count Cuts

Increment chunk count at each valid cut position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* arr, int n) {
    if (n == 0) {
        return 0;
    }
    
    int* sortedArr = malloc(n * sizeof(int));
    memcpy(sortedArr, arr, n * sizeof(int));
    qsort(sortedArr, n, sizeof(int), compare);
    
    int chunks = 0;
    int maxSoFar = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxSoFar) {
            maxSoFar = arr[i];
        }
        
        // If max in first i+1 elements equals (i+1)th smallest element,
        // we can make a cut after position i
        if (maxSoFar == sortedArr[i]) {
            chunks++;
        }
    }
    
    free(sortedArr);
    return chunks;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int arr[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), single scan takes O(n)

⚡ Linearithmic

Space Complexity

O(n)

Additional array needed to store sorted version

⚡ Linearithmic Space

89.3K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach with Prefix Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler