Beats 100% 🔥 | Easy & Intuitive Solution 💡 | Clean Code Explained 🚀
IntuitionThe key to solving this problem is understanding that each "chunk" is a segment of the array where all elements can be sorted independently to form par
# Intuition
The key to solving this problem is understanding that each "chunk" is a segment of the array where all elements can be sorted independently to form part of the sorted array. To determine when a chunk ends, we need to check if the cumulative difference between the sorted array and the original array is zero up to that point. If the difference becomes zero, it indicates that all elements up to that index can form a valid chunk.

# Approach
1. **Copy and Sort**: First, create a copy of the input array and sort it. This gives us the reference for the target order.
2. **Track Difference**: Use a variable `dif` to track the cumulative difference between the sorted and the original arrays at each index.  
   - For each element, update `dif` by adding the difference between the corresponding elements of the sorted array and the original array.
3. **Check for Chunks**: If `dif` becomes zero at any index, it means that all elements up to that index in the original array can be sorted independently to match the sorted array.
4. **Count Chunks**: Increment the `count` whenever `dif` is zero.
5. **Return Result**: At the end, `count` gives the maximum number of chunks.

# Complexity
- **Time complexity**:  
  Sorting the array takes $$O(n \log n)$$, and iterating through the array takes $$O(n)$$.  
  Therefore, the overall complexity is $$O(n \log n)$$.
  
- **Space complexity**:  
  The additional space used is $$O(n)$$ for storing the copy of the array. Thus, the space complexity is $$O(n)$$.

# Code
```cpp
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        vector<int> dum = arr;
        sort(arr.begin(), arr.end());
        long long dif = 0;
        int count = 0, n = arr.size();
        for(int i=0; i<n; i++){
            dif += (arr[i]-dum[i]);
            count += (dif==0);
        }
        return count;
    }
};

['C++']