Next Permutation in Python

Problem Statement

A permutation of an array of integers is an arrangement of its elements.

The next permutation is the next lexicographically greater arrangement of the array. If no such permutation exists (the array is in descending order), we rearrange it into the smallest possible order (ascending order).

Examples:

Input: [1, 2, 3] - Output: [1, 3, 2]
Input: [3, 2, 1] - Output: [1, 2, 3]
Input: [1, 1, 5] - Output: [1, 5, 1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

The solution must modify the array in-place and use constant extra memory.

Approach

Find the pivot:
Traverse the array from right to left and find the first element that is smaller than its next element. This is the pivot we need to increase.

Find the successor:
From the right end, find the first element greater than the pivot.

Swap pivot and successor:
Swap these two elements.

Reverse the suffix:
Reverse the subarray to the right of the pivot index. This ensures the suffix is in ascending order, giving the next smallest permutation.

Python CODE

class Solution:
def nextPermutation(self, nums):
n = len(nums)
i = n - 2

    # Step 1: Find the first decreasing element from the right
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: Find the number just larger than nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Step 3: Swap them
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: Reverse the numbers after i
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Example Test Cases

sol = Solution()

nums1 = [1, 2, 3]
sol.nextPermutation(nums1)
print(nums1)

Output: [1, 3, 2]

nums2 = [3, 2, 1]
sol.nextPermutation(nums2)
print(nums2)

Output: [1, 2, 3]

nums3 = [1, 1, 5]
sol.nextPermutation(nums3)
print(nums3)

Output: [1, 5, 1]

Explanation of Example [1, 2, 3]
Pivot = 2 (index 1, since 2 < 3)
Successor = 3
Swap - [1, 3, 2]
Reverse suffix (only 2 in this case) - [1, 3, 2]

This logic works for any array, including arrays with duplicate elements.
Always traverse from right to left to find the first decreasing number for the next permutation.
Swapping and reversing ensures minimal changes to achieve the next greater sequence.
Works for arrays with duplicates and modifies in place.