Rearrange the numbers into the next permutation, the next arrangement in dictionary order. If the array is already the largest arrangement, wrap around to the smallest one. Do it in place, with constant extra space.
DSA Animator › DSA Revision › Arrays › Next Permutation
Remember: 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. The video solves Next Permutation (LeetCode 31, Medium) with the Array Manipulation pattern from the Arrays topic, and you can replay every step in the interactive Next Permutation animation.
Rearrange the numbers into the next permutation, the next arrangement in dictionary order. If the array is already the largest arrangement, wrap around to the smallest one. Do it in place, with constant extra space.
For 1, 3, 5, 4, 2, the next permutation is 1, 4, 2, 3, 5. It is the smallest arrangement that is still bigger than the original.
Listing every permutation and finding the next one is O of 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.
Scanning from the right, 2, 4 and 5 keep increasing as we move left. Then 3 is smaller than 5, so the pivot is 3, at index 1. From the right, the first number bigger than 3 is 4, at index 3. Swap them, and the array becomes 1, 4, 5, 3, 2. The part after the pivot, 5, 3, 2, is decreasing, so reverse it to 2, 3, 5. The answer is 1, 4, 2, 3, 5.
In code, move i left while the value at i is not smaller than the value after it. If a pivot exists, move j left from the end until it finds a value bigger than the pivot, and swap. Finally reverse everything after index i. If there was no pivot, that reverse turns the largest arrangement into the smallest, so it's O of n time and O of 1 space.
Remember: 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.