Vultr DocsLatest Content

Max Chunks To Make Sorted

Updated on 13 June, 2025
Max Chunks To Make Sorted header image

Problem Statement

Given an integer array arr (of length n), which is a permutation of the integers in the range [0, n - 1], our goal is to split this array into several non-overlapping "chunks" (or partitions). Each chunk, when sorted independently and then concatenated back together, should form the correctly sorted array (i.e., [0, 1, 2, ..., n-1]). The challenge is to determine the maximum number of chunks we can create from the array such that when they are separately sorted and reassembled, they still produce the sorted array.

Examples

Example 1

Input:

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

Output:

1

Explanation:

Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2

Input:

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

Output:

4

Explanation:

We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Constraints

  • n == arr.length
  • 1 <= n <= 10
  • 0 <= arr[i] < n
  • All the elements of arr are unique.

Approach and Intuition

  1. Each index in the array can be used as a guide to determine a valid chunk boundary. If a chunk can be confirmed as individually sortable within its segment to align with its final sorted state, it can be considered as a chunk. The goal is to maximize such chunks.
  2. Start traversing the array and maintain a record of the maximum element observed till the current index. If at any index, the maximum element observed so far is equal to the current index (as the array is a permutation of numbers from 0 to n-1), a chunk boundary can be established.
  3. Splitting logic can be deduced from the examples:
    • For arr = [4,3,2,1,0], despite the reverse order, the whole array is a single chunk because any internal partitioning breaks the consecutive sequence due to the disorder.
    • For arr = [1,0,2,3,4], smaller chunks like [1, 0], [2], [3], and [4] can be sorted independently and still form part of the larger sorted sequence.
  4. Understanding that each valid partition point (or chunk boundary) is where the array’s element values can align sequentially and up to that point all numbers are present eases the decision for a split.
  5. With small maximum array size constraints (max.length = 10), this method is computationally feasible. For each observation, check if the maximum value equals the current index, incrementing a chunk count whenever this holds true.

The challenge primarily revolves around recognizing these partition points and ensuring that at each potential chunk end, the maximum of the included elements matches the criteria for forming a contiguous sorted sequence after that point.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int calculateMaxChunks(vector<int>& numbers) {
        int length = numbers.size();
        int countChunks = 0, highest = 0;

        for (int index = 0; index < length; index++) {
            highest = max(highest, numbers[index]);
            if (highest == index) {
                countChunks++;
            }
        }

        return countChunks;
    }
};

The given C++ solution is designed to solve the problem of determining the maximum number of "chunks" an array can be divided into such that, when each chunk is sorted individually, the entire array becomes sorted. This method is efficiently implemented in the calculateMaxChunks function.

Here's a breakdown of the approach:

  • Initialize a counter countChunks to track the number of valid chunks and a variable highest to keep track of the maximum value encountered as the array is iterated.
  • Iterate through the array using an index index. For each element:
    • Update highest to be the maximum value between the current element and the previously recorded highest value.
    • If the current highest number equals the current index position, increment the countChunks counter. This condition checks if a chunk can be closed off here.
  • Return the value of countChunks which represents the maximum chunks in which the array can be divided to meet the sorting condition.

By implementing this strategy, the function can identify the correct position to split the array into independently sortable chunks, hence optimizing the sorting process.

java 
class Solution {

    public int maxSortedChunks(int[] array) {
        int length = array.length;
        int chunkCount = 0, maxSoFar = 0;

        for (int index = 0; index < length; index++) {
            maxSoFar = Math.max(maxSoFar, array[index]);

            if (maxSoFar == index) {
                chunkCount++;
            }
        }

        return chunkCount;
    }
}

In the provided Java solution for the problem "Max Chunks To Make Sorted," the program strategically divides an array into the maximal number of "sorted chunks." Each chunk, when individually sorted, allows the entire set to be sorted once combined.

  • The method maxSortedChunks(int[] array) processes an input array to determine the number of maximal chunks that can be created:
    • length stores the size of the array.
    • chunkCount keeps track of the number of chunks.
    • maxSoFar captures the highest value encountered as the array is iterated through.
  • Iterate through the array:
    • Update maxSoFar to the maximum of itself and the current array element.
    • If maxSoFar equals the current index, increment chunkCount.
  • Return chunkCount as the result, representing the maximum chunks the array can be split into and individually sorted to form a globally sorted structure.

With this approach, one efficiently calculates the suitable partition points by leveraging the property that if the maximum value up to a point is equal to the index, the segment up to that index can independently be sorted to contribute towards a globally sorted array. This ensures optimal placement and minimal computational complexity.

python 
class Solution:
    def divideIntoSortedChunks(self, arr):
        arr_length = len(arr)
        num_chunks = 0
        current_max = 0

        for index in range(arr_length):
            current_max = max(current_max, arr[index])
            
            if current_max == index:
                num_chunks += 1

        return num_chunks

The provided Python solution aims to solve the problem of determining how many chunks a list can be divided into, such that sorting these chunks individually results in the entire list being sorted. The solution involves iterating through the list and counting chunks based on a specific condition.

Here's a concise breakdown of how the solution operates:

  • Initialize two variables, num_chunks to count the number of chunks and current_max to keep track of the maximum number seen so far in the array.
  • Iterate through the array using a for loop. For each element:
    • Update current_max to be the larger of current_max or the current element.
    • If current_max equals the current index, increment the num_chunks counter by one.
  • Return the count of chunks after the loop completes.

This approach ensures that a new chunk is considered each time the maximum element encountered so far matches the current position in the array, indicating that all previous elements can be sorted independently up to this point. This technique leverages the properties of the indices and values to efficiently determine the optimal chunk division for sorting.

Comments

No comments yet.