CA 12 - Next Permutation

Problem

Given an array.
You need to change it to the next bigger arrangement

---

Example:

[1,2,3] → [1,3,2]
[1,3,2] → [2,1,3]
[3,2,1] → 1,2,3

Correct Idea (Very Simple)

“Where can I make the number slightly bigger?”

---

Steps

1. Find the first decrease (from right)
   Find index i such that:
   nums[i] < nums[i+1]

2. Find next bigger number (from right)
   Find a number just greater than nums[i]

3. Swap
   Swap both numbers

4. Reverse the right side
   Make the right side smallest (ascending)

Example
nums = [1,3,2]

Step by step:

• Find pivot → 1
• Find next bigger → 2
• Swap → [2,3,1]
• Reverse → [2,1,3]

Code:
class Solution(object):
def nextPermutation(self, nums):
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1:] = reversed(nums[i+1:])