Next Permutation

▶

Steps

setup

Initialize pointer i to find pivot

Set pointer i to the second last index (1) to start scanning from right to left to find the pivot where nums[i] < nums[i+1].

💡 Starting from the right helps find the first place where the sequence stops increasing, which is the pivot point for the next permutation.

Line:

i = len(nums) - 2

💡 The pivot is the first element from the right that can be increased to get the next permutation.

compare

Check if nums[i] >= nums[i+1], move i left if true

Compare nums[1] (2) and nums[2] (3). Since 2 < 3, the condition nums[i] >= nums[i+1] is false, so stop moving i.

💡 This comparison finds the pivot where the sequence stops increasing from the right.

Line:

while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1

💡 Pivot found at index 1 where nums[i] < nums[i+1].

setup

Initialize pointer j to find successor

Set pointer j to the last index (2) to find the rightmost successor to pivot that is greater than nums[i].

💡 The successor is the smallest number larger than the pivot to swap with for the next permutation.

Line:

j = len(nums) - 1

💡 Starting from the right ensures the successor is the rightmost element greater than pivot.

compare

Check if nums[j] <= nums[i], move j left if true

Compare nums[2] (3) and nums[1] (2). Since 3 > 2, the condition nums[j] <= nums[i] is false, so stop moving j.

💡 We want the rightmost element greater than pivot to swap with.

Line:

while nums[j] <= nums[i]:
    j -= 1

💡 Successor found at index 2.

swap

Swap pivot and successor

Swap the values at indices i (1) and j (2), swapping 2 and 3 to move closer to the next permutation.

💡 Swapping pivot with successor increases the permutation minimally.

Line:

nums[i], nums[j] = nums[j], nums[i]

💡 After swap, prefix is fixed and suffix needs reversal to get next permutation.

setup

Initialize pointers left and right for suffix reversal

Set left to i+1 (2) and right to last index (2) to reverse the suffix after pivot.

💡 Reversing the suffix puts it in ascending order for the next permutation.

Line:

left, right = i + 1, len(nums) - 1

💡 Suffix starts at index 2 and ends at index 2, currently a single element.

compare

Check if left < right to reverse suffix

Compare left (2) and right (2). Since left is not less than right, no reversal needed.

💡 If suffix length is 1 or 0, it is already reversed.

Line:

while left < right:

💡 Suffix is already in ascending order after swap.

move_left|move_right

Confirm no swap needed for suffix reversal

Since left is not less than right, no swap or pointer movement occurs; suffix reversal is complete.

💡 No pointer moves or swaps means suffix is already in correct order.

Line:

while left < right:
    # no iterations since condition false

💡 Suffix reversal loop skipped as suffix length is 1.

reconstruct

Next permutation complete

The array now represents the next permutation [1,3,2]. The algorithm finishes here.

💡 The final array is the next lexicographical permutation after the input.

Line:

return (implicit after reversal)

💡 Next permutation found without generating all permutations.

reconstruct

Read final answer

The final array [1,3,2] is the next permutation after [1,2,3].

💡 This is the output the algorithm produces for the given input.

Line:

print(arr)  # Output: [1,3,2]

💡 The algorithm successfully computed the next permutation in-place.

def next_permutation(nums):
    i = len(nums) - 2  # STEP 1: Initialize i
    while i >= 0 and nums[i] >= nums[i + 1]:  # STEP 2: Find pivot
        i -= 1
    if i >= 0:
        j = len(nums) - 1  # STEP 3: Initialize j
        while nums[j] <= nums[i]:  # STEP 4: Find successor
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]  # STEP 5: Swap pivot and successor
    left, right = i + 1, len(nums) - 1  # STEP 6: Initialize left and right
    while left < right:  # STEP 7: Reverse suffix
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

if __name__ == '__main__':
    arr = [1,2,3]
    next_permutation(arr)  # STEP 8: Compute next permutation
    print(arr)  # STEP 9: Output result

📊

Next Permutation - Watch the Algorithm Execute, Step by Step

Watching each pointer move and swap helps you understand how the algorithm transforms the array in-place to the next permutation without generating all permutations.

setup

1

0

i

2

1

3

2

compare

1

0

i

2

1

3

2

setup

1

0

i

2

1

j

3

2

compare

1

0

i

2

1

j

3

2

swap

1

0

i

3

1

j

2

2

setup

1

0

3

1

right

2

2

compare

1

0

3

1

right

2

2

move_left

1

0

3

1

right

2

2

reconstruct

1

0

3

1

2

2

Result: [1,3,2]

reconstruct

1

0

3

1

2

2

Result: [1,3,2]

Key Takeaways

✓ The pivot is the first element from the right that breaks the descending order.

This is hard to see from code alone because the while loop hides the scanning process.

✓ Swapping the pivot with the rightmost successor greater than it ensures the next permutation is just one step higher.

Visualizing the pointers shows why the successor must be the rightmost element greater than the pivot.

✓ Reversing the suffix after the pivot places it in ascending order, completing the next permutation.

Without visualization, it's not obvious why reversing the suffix is necessary after swapping.