769. Max Chunks To Make Sorted

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.

Approach 01:

#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int chunksCount = 0;
        int maxElement = INT_MIN;

        for (int currentIndex = 0; currentIndex < arr.size(); ++currentIndex) {
            maxElement = max(maxElement, arr[currentIndex]);
            if (maxElement == currentIndex) {
                ++chunksCount;
            }
        }

        return chunksCount;
    }
};

class Solution:
    def maxChunksToSorted(self, arr):
        chunksCount = 0
        maxElement = float('-inf')

        for currentIndex in range(len(arr)):
            maxElement = max(maxElement, arr[currentIndex])
            if maxElement == currentIndex:
                chunksCount += 1

        return chunksCount

• Iterating Through the Array:
  • The array arr is iterated once, and for each element, the maximum value up to the current index is calculated using the max function.
  • This operation takes \(O(n)\) time, where \(n\) is the size of the input array.
• Overall Time Complexity:

  The total time complexity is \(O(n)\), as the array is traversed once, and each operation within the loop is \(O(1)\).

Space Complexity

• Input Storage:
  • The input array arr requires \(O(n)\) space.
• Auxiliary Variables:
  • Two integer variables, chunksCount and maxElement, are used, which require \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(1)\), as the extra space used does not depend on the size of the input array.