DEV Community

Cover image for 769. Max Chunks To Make Sorted
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1

769. Max Chunks To Make Sorted

769. Max Chunks To Make Sorted

Difficulty: Medium

Topics: Array, Stack, Greedy, Sorting, Monotonic Stack

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.

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.

Hint:

  1. The first chunk can be found as the smallest k for which A[:k+1] == [0, 1, 2, ...k]; then we repeat this process.

Solution:

We need to find the largest number of chunks that can be formed such that each chunk can be sorted individually, and when concatenated, the result is the sorted version of the entire array.

Approach:

  1. Key Observation:

    • The array is a permutation of integers from 0 to n-1. The idea is to traverse the array and find positions where the chunks can be separated.
    • A chunk can be sorted if, for all indices within the chunk, the maximum element up to that point does not exceed the minimum element after that point in the original sorted array.
  2. Strategy:

    • Track the maximum value encountered as you traverse from left to right.
    • At each index i, check if the maximum value up to i is less than or equal to i. If this condition holds, it means you can split the array at that index because the left part can be sorted independently.
  3. Steps:

    • Iterate over the array while maintaining the running maximum.
    • Whenever the running maximum equals the current index, a chunk can be made.
    • Count the number of such chunks.

Let's implement this solution in PHP: 769. Max Chunks To Make Sorted

<?php
/**
 * @param Integer[] $arr
 * @return Integer
 */
function maxChunksToSorted($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$arr1 = [4, 3, 2, 1, 0];
$arr2 = [1, 0, 2, 3, 4];

echo maxChunksToSorted($arr1); // Output: 1
echo "\n";
echo maxChunksToSorted($arr2); // Output: 4
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Initialization:

    • We start with maxSoFar = -1 to ensure that we correctly track the maximum value in the array as we traverse it.
    • chunks = 0 keeps track of the number of chunks that can be formed.
  2. Loop:

    • We loop through each element in the array.
    • For each element, we update the maxSoFar to be the maximum value between the current element and the previously seen maximum.
    • If maxSoFar == i, it means the array up to index i can be independently sorted and this is a valid chunk.
    • We increment the chunk count each time this condition holds true.
  3. Return:

    • Finally, the total number of chunks is returned.

Time Complexity:

  • Time Complexity: O(n), where n is the length of the array. We only make one pass through the array.
  • Space Complexity: O(1), as we are only using a few variables to store intermediate results.

Example Walkthrough:

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

  • At index 0, the maximum value encountered so far is 1. We can't split here.
  • At index 1, the maximum value is 1, which matches the current index 1, so we can split into a chunk.
  • At index 2, the maximum value is 2, and it matches the index 2, so we split again.
  • At index 3, the maximum value is 3, and it matches the index 3, so we split again.
  • At index 4, the maximum value is 4, and it matches the index 4, so we split again.

Thus, the output for this case is 4 because we can split it into 4 chunks.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI

Automatic Speech Recognition with AssemblyAI

Experience near-human accuracy, low-latency performance, and advanced Speech AI capabilities with AssemblyAI's Speech-to-Text API. Sign up today and get $50 in API credit. No credit card required.

Try the API

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay