Max Chunks To Make Sorted LeetCode

 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.

Approach 1 :

Using Left Max and Right Min Arrays

Idea:

Instead of tracking only the maximum, we can also maintain the right minimum values.

• leftMax[i]: Stores the maximum value from index 0 to i.

• rightMin[i]: Stores the minimum value from index i to n-1.

• A valid chunk is where leftMax[i] <= rightMin[i+1], meaning all elements in the left partition are smaller than the right partition.

Steps:

1. Compute leftMax[] such that leftMax[i] stores the maximum element from 0 to i.

2. Compute rightMin[] such that rightMin[i] stores the minimum element from i to n-1.

3. Count the chunks where leftMax[i] <= rightMin[i+1].

class Solution {

    public int maxChunksToSorted(int[] arr) {

       

        int n = arr.length;

        int[] leftmax = new int[n]; // Array to store the maximum values from left to current index

        int[] rightmin = new int[n]; // Array to store the minimum values from current index to right

       

        // Initialize leftmax array

        leftmax[0] = arr[0];

        for (int i = 1; i < n; i++) {

            // leftmax[i] stores the maximum value from index 0 to i

            leftmax[i] = Math.max(leftmax[i - 1], arr[i]);

        }

        // Initialize rightmin array

        rightmin[n - 1] = arr[n - 1];

        for (int i = n - 2; i >= 0; i--) {

            // rightmin[i] stores the minimum value from index i to n-1

            rightmin[i] = Math.min(rightmin[i + 1], arr[i]);

        }

        int chunk = 0; // Count the number of valid chunks

        // Iterate through the array to find valid chunking points

        for (int i = 0; i < n - 1; i++) {

            // If the max in the left partition is smaller than the min in the right partition,

            // it means we can form a valid chunk

            if (leftmax[i] < rightmin[i + 1]) {

                chunk++;

            }

        }

        // The final chunk count is incremented by 1 because the last segment is always a chunk

        return chunk + 1;

    }

}

Approach 2:-

Intuition:

We don't need extra arrays (leftmax and rightmin) to find the maximum chunks. Instead, we can track the maximum value seen so far while iterating through the array.

Key Observations:

• If, at any index i, the maximum element so far (maxSoFar) is equal to i, then all elements from index 0 to i form a valid chunk.

• This is because, in a sorted version of the array, elements 0 to i must be in the range [0, i], ensuring that they are already in their correct relative order.

Algorithm:

1. Initialize maxSoFar = 0 and chunks = 0.

2. Iterate through the array:

   • Update maxSoFar = max(maxSoFar, arr[i]) to track the maximum element seen so far.

   • If maxSoFar == i, it means elements from 0 to i form a valid chunk, so increase chunks.

3. Return chunks at the end.

class Solution {

    public int maxChunksToSorted(int[] arr) {

         int maxSoFar = 0, chunks = 0;

        for (int i = 0; i < arr.length; i++) {

            maxSoFar = Math.max(maxSoFar, arr[i]); // Track the max element seen so far

            if (maxSoFar == i) { // If maxSoFar equals the current index, we can form a chunk

                chunks++;

            }

        }

        return chunks;

    }

}