C++ Easy Sorting
Intuition\nThe last number that belongs to the chunk should be present at that index or before that index.\n\nbefore sorting [array, index] :{{2,0},{1,1},{3,2},
# Intuition\nThe last number that belongs to the chunk should be present at that index or before that index.\n\nbefore sorting [array, index] :{{2,0},{1,1},{3,2},{4,3},{4,4}}\nafter sorting.... [array, index] :{{1,1},{2,0},{3,2},{4,3},{4,4}}\n\nNow, while traversing the sorted array arr[n][2], we know that we need to include elements upto arr[i][1](the index in the original array) in the chunk for it to come at the right place after sorting chunk wise. \n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int maxChunksToSorted(vector<int>& nums) {\n        int n = nums.size(), max_index = 0, ans = 0; \n        vector<vector<int>> v;  \n        for(int i=0; i<n; i++){\n            v.push_back({nums[i], i}); \n        }\n        sort(v.begin(), v.end());\n        for(int i=0; i<n; i++){\n            max_index = max(max_index, v[i][1]); \n            if(i==max_index) ans++;\n        }\n        return ans;\n    }\n};\n```
['Sorting', 'C++']