Loop Array Hash Map Counting Prefix Sum
Intermediate Level

Implement the nextPermutationRankChange method that returns the next lexicographical permutation of the array.

The input contains an integer array nums and its length size. The array represents a permutation of numbers.

Your task is to return the next lexicographically greater permutation. If the current permutation is already the greatest possible order, return the smallest order by arranging the numbers in ascending order.

Example 1
Input:
nums (int[]) = [1,2,3]
size (int) = 3
Return:
(int[]) [1,3,2]
Example 2
Input:
nums (int[]) = [3,2,1]
size (int) = 3
Return:
(int[]) [1,2,3]
Example 3
Input:
nums (int[]) = [1,1,5]
size (int) = 3
Return:
(int[]) [1,5,1]

Start from the right side and find the first position where nums[i] is smaller than nums[i + 1]. This position is the pivot where the next permutation can be made larger.

Then find the smallest number on the right side that is greater than the pivot value, swap both values, and reverse the suffix after the pivot.

If no pivot is found, the array is in descending order, so reverse the whole array to get the smallest permutation.

Pseudocode:

function nextPermutationRankChange(nums, size):
    i = size - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i--
    if i >= 0:
        j = size - 1
        while nums[j] <= nums[i]:
            j--
        swap nums[i] and nums[j]
    reverse nums from index i + 1 to size - 1
    return nums
Run your code to see the result.