Q8: 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:
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.
Solution:
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int n=arr.size();
int ans=0;
int currmax=arr[0];
for(int i=0;i<n;i++){
if(arr[i]>currmax){
currmax=arr[i];
}
if(currmax==i){
ans++;
}
}
return ans;
}
};
Explantion:
// Get the size of the input array
// Initialize a variable to store the answer (maximum chunks)
// Initialize a variable to track the maximum element encountered so far
//Loop through each element in the input array.
//If the current element is greater than the current maximum,update currmax to
the current element.
//If the current maximum (currmax) is equal to the current index i, it indicates
a potential chunk boundary where elements from 0 to i are in sorted order.
Increment the ans counter.
//Return the total number of chunks found
If anyone have better solution so please comment:)