Max Chunks To Make Sorted - Practice Coding Problems

Max Chunks To Make Sorted - Problem

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].

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 — Maximum Chunks

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

› Output: 1

💡 Note: The array is completely reverse sorted. We need the maximum element 4 to reach its correct position at index 4, so we can only make 1 chunk containing all elements.

Example 2 — Multiple Chunks

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

› Output: 4

💡 Note: We can split into chunks: [1,0] (sorts to [0,1]), [2], [3], [4]. After concatenating: [0,1,2,3,4] which is the sorted array.

Example 3 — Already Sorted

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

› Output: 5

💡 Note: Array is already sorted, so each element can be its own chunk: [0], [1], [2], [3], [4].

Constraints

n == arr.length
1 ≤ n ≤ 10
arr is a permutation of [0, 1, ..., n - 1]

Visualization

Tap to expand

Understanding the Visualization

Input Array

Permutation of integers [0, n-1] in some order

Find Chunks

Identify positions where we can split the array

Verify Result

Sorting each chunk and concatenating gives sorted array

Key Takeaway

🎯 Key Insight: We can end a chunk at position i when max(arr[0..i]) equals i, ensuring all elements 0 to i are present in the first i+1 positions.

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is that for a permutation array, we can create a chunk at position i if the maximum element from start to i equals i. This guarantees all elements 0 to i are present. Best approach is the greedy algorithm with one pass. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Partitions	O(2^n × n log n)	O(n)	Generate all possible ways to split the array and check which ones work
Greedy - Track Maximum Element	O(n)	O(1)	Create a chunk whenever the maximum element seen so far equals the current index

Brute Force - Try All Partitions — Algorithm Steps

Step 1: Generate all possible partition combinations using bit masks
Step 2: For each partition, sort chunks individually and check if result equals sorted array
Step 3: Return the maximum valid chunk count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Use bit masks to create all possible chunk divisions

Test Each Partition

Sort chunks individually and verify result

Find Maximum

Return the largest valid chunk count

Code -

solution.c — C

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

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

int solution(int* arr, int n) {
    int maxChunks = 0;
    
    // Try all possible partitions using bit mask
    for (int mask = 0; mask < (1 << (n - 1)); mask++) {
        int* result = (int*)malloc(n * sizeof(int));
        int resultIdx = 0;
        int start = 0;
        int chunkCount = 0;
        
        // Create chunks based on bit mask
        for (int i = 0; i < n - 1; i++) {
            if (mask & (1 << i)) {
                int chunkSize = i + 1 - start;
                int* chunk = (int*)malloc(chunkSize * sizeof(int));
                for (int j = 0; j < chunkSize; j++) {
                    chunk[j] = arr[start + j];
                }
                qsort(chunk, chunkSize, sizeof(int), compare);
                for (int j = 0; j < chunkSize; j++) {
                    result[resultIdx++] = chunk[j];
                }
                free(chunk);
                start = i + 1;
                chunkCount++;
            }
        }
        
        // Handle last chunk
        int lastChunkSize = n - start;
        int* lastChunk = (int*)malloc(lastChunkSize * sizeof(int));
        for (int j = 0; j < lastChunkSize; j++) {
            lastChunk[j] = arr[start + j];
        }
        qsort(lastChunk, lastChunkSize, sizeof(int), compare);
        for (int j = 0; j < lastChunkSize; j++) {
            result[resultIdx++] = lastChunk[j];
        }
        free(lastChunk);
        chunkCount++;
        
        // Check if result equals sorted array
        int* sorted = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            sorted[i] = arr[i];
        }
        qsort(sorted, n, sizeof(int), compare);
        
        int valid = 1;
        for (int i = 0; i < n; i++) {
            if (result[i] != sorted[i]) {
                valid = 0;
                break;
            }
        }
        
        if (valid && chunkCount > maxChunks) {
            maxChunks = chunkCount;
        }
        
        free(result);
        free(sorted);
    }
    
    return maxChunks;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n log n)

2^n partitions to try, each requiring O(n log n) sorting verification

⚠ Quadratic Growth

Space Complexity

O(n)

Space for temporary arrays during sorting verification

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~15 min Avg. Time

2.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

Brute Force - Try All Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler