algoadvance

Leetcode 769. Max Chunks To Make Sorted

Problem Statement

You are given an array of integers arr which represents a permutation of the first n positive integers, where n is the array’s length. You need to partition the array into a maximum number of “chunks” (partitions), which can be individually sorted, and after concatenating them, the entire array returns to being sorted in increasing order.

Return the maximum number of chunks we can partition the array into.

Example

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

Constraints

• n == arr.length
• 1 <= n <= 10^4
• 0 <= arr[i] < n
• All the integers in arr are unique.

Clarifying Questions

1. Can the array have negative numbers?
   No, the array consists of the first n positive integers (including zero).
2. Is the input guaranteed to be a permutation of the first n positive integers?
   Yes.

Strategy

To determine the maximum number of chunks, we can use a greedy algorithm. The key observation is that we can form a chunk ending at index i if the maximum value of the elements in the chunk so far is i. This ensures that all numbers up to i have appeared in the segment, and thus it can be sorted independently.

Here’s a step-by-step strategy:

1. Initialize max_so_far to 0 and count_chunks to 0.
2. Iterate through the array.
3. For each index i, update max_so_far to be the maximum value observed so far.
4. If max_so_far equals the current index i, it means all values up to i have been encountered, and we can form a chunk ending at index i. Increment the chunk counter.
5. Return count_chunks at the end.

Code

Here’s the implementation of the strategy in Java:

public class Solution {
    public int maxChunksToSorted(int[] arr) {
        int maxSoFar = 0;
        int countChunks = 0;

        for (int i = 0; i < arr.length; i++) {
            maxSoFar = Math.max(maxSoFar, arr[i]);
            if (maxSoFar == i) {
                countChunks++;
            }
        }
        
        return countChunks;
    }
}

Explanation

• maxSoFar: Tracks the maximum value encountered so far in the iteration.
• countChunks: Counts the number of valid chunks.
• As we iterate through the array, we update maxSoFar with the maximum of itself and the current element.
• Whenever maxSoFar equals the current index i, it indicates that all numbers up to i are within this segment, making it a valid chunk.

Time Complexity

• The time complexity is O(n) because we only need a single pass through the array to determine the maximum number of chunks.
• The space complexity is O(1) as we utilize a fixed amount of additional space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?