Rearrange nums into the next greater permutation in dictionary order. If it's already the largest arrangement, wrap around to the smallest (sorted ascending). Do it in place with O(1) extra memory.
nums = [1,2,3][1,3,2]nums = [3,2,1][1,2,3] (largest → wraps to smallest)nums = [1,1,5][1,5,1]i with nums[i] < nums[i+1] 🔻j with nums[j] > nums[i], then swap them 🔄nums[i+1..] so the suffix becomes ascending ↩️After the swap, the suffix is still descending: the new value at j fits between its neighbours because it's the smallest number bigger than the pivot. So "sort the suffix ascending" is just reversing it, O(n) instead of O(n log n). And the first j from the right with nums[j] > nums[i] is automatically the smallest such number, because the suffix is descending.
Fully descending ([3,2,1]) → no dip, reverse everything to get [1,2,3]. Duplicates ([1,1,5], [1,5,1]) → use >= when looking for the dip and <= when looking for j, or equal values get swapped for nothing. Single element → unchanged.
Listing every permutation and finding the next one is O(n) factorial. We only need to change as little as possible, as far right as possible.
Scan from the right to find the first number that is smaller than the number after it. This is the pivot: everything to its right is in decreasing order, so that part is already at its maximum. Swap the pivot with the smallest number on its right that is still bigger than it. Then reverse the part after the pivot, so it becomes as small as possible.
Find the pivot from the right, swap it with the next bigger value, then reverse the suffix. The suffix after the pivot is always decreasing.
Run the animation above on your own input, or watch the 1:52 video explanation of Next Permutation with a dry run and Java code.