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.length1 <= n <= 100 <= arr[i] < narr are unique.In this approach, we iterate over the array using a pointer. We track the maximum element we've seen at each point. Every time the maximum element seen so far equals the current index, it signifies that a chunk can end here. The chunk defined between the previous chunk's end and the current index can be sorted alone to align with the sorted array.
We declare variables to track the maximum value encountered and the count of chunks. As we iterate, if we reach a point where the maximum value is equal to the index, it represents the end of a chunk, and we increment the count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as we only use constant extra space.
This approach involves first sorting the original array and using a sorted version to compare and identify zero-sum ranges. By keeping a cumulative sum difference between the original array and the sorted array, chunks can be identified at points where this cumulative sum is zero, indicating matching segments that can form a chunk.
We copy and sort the array. By comparing cumulative sums of the original and sorted arrays, each zero-sum segment signifies a chunk.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the sorted array copy.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Max Tracking | Time Complexity: O(n), where n is the length of the array. |
| Approach 2: Sort and Compare | Time Complexity: O(n log n) due to sorting. |
Max Chunks To Make Sorted - Leetcode 769 - Python • NeetCodeIO • 8,045 views views
Watch 9 more video solutions →Practice Max Chunks To Make Sorted with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor