class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        // Find the anchor where a[i] < a[i+1]
        int anchor = -1;
        int n = nums.size();

        for(int i = 0; i < n - 1; i++) {
            if(nums[i] < nums[i+1]) anchor = i;
        }

        if(anchor == -1) {
            // That means the array is sorted in increasing fashion,
            // reverse the array
            return std::reverse(nums.begin(), nums.end());
        }

        // After finding the anchor index, find the next greater
        // element than anchor, by traversing through the end to start
        for(int i = n-1; i > anchor; i--) {
            if(nums[i] > nums[anchor]) {
                // Swap the anchor element and the next greater
                int temp = nums[anchor];
                nums[anchor] = nums[i];
                nums[i] = temp;
                break;
            }
        }
        return std::reverse(nums.begin() + anchor + 1, nums.end());
    }
};