Next Permutation

Next Permutation — LeetCode

Rearrange the array into the next lexicographically greater permutation in place. If no such permutation exists, rearrange it into the lowest (sorted) order.

Approach

1. Start from last, go backwards till there is a dip (nums[i] < nums[i+1]). Store i in pivot

2. If pivot > -1, find the smallest element that is > nums[pivot] at the farthest position (meaning, nums[pivot] < nums[j] && nums[j] <= nums[currentMinimumIndex]). Swap the pivot with the index of the minimum element.

3. Reverse the right portion of the array

Remarks

I would never come up with this solution on my own...

https://youtu.be/JDOXKqF60RQ?si=HsOnMMnOuR3wXGa\_

Related

• Arrays and Hashing
• Generate all permutations