LeetCode 31: Next Permutation Solution in Python Explained

Problem Statement

LeetCode 31, Next Permutation, is a medium-level problem where you’re given an array of integers nums representing a permutation of numbers. Your task is to modify the array in-place to form the next lexicographically greater permutation. If no greater permutation exists (i.e., the array is the last permutation), rearrange it to the smallest permutation (sorted in ascending order). The solution must be in-place with O(1) extra space.

Constraints

1 <= nums.length <= 100: Array length is between 1 and 100.
0 <= nums[i] <= 100: Each element is between 0 and 100.

Example

Input: nums = [1,2,3]
Output: [1,3,2]
Explanation: Next permutation after [1,2,3] is [1,3,2].

Input: nums = [3,2,1]
Output: [1,2,3]
Explanation: [3,2,1] is the last permutation, so reset to [1,2,3].

Input: nums = [1,1,5]
Output: [1,5,1]
Explanation: Next permutation after [1,1,5] is [1,5,1].

Understanding the Problem

How do you solve LeetCode 31: Next Permutation in Python? For nums = [1,2,3], the next permutation is [1,3,2]—the smallest increase in lexicographical order. For [3,2,1], it’s the last permutation, so reset to [1,2,3]. We’ll explore two approaches: an Optimal In-Place Solution (primary, using a specific algorithm) and an Alternative with Generate-and-Find (intuitive but less efficient). The optimal solution finds the next permutation by swapping and reversing in-place.

Solution 1: Optimal In-Place Approach (Primary)

Explanation

To find the next permutation: 1. Locate the first pair from the right where nums[i] < nums[i+1]—this is the pivot point to increase. 2. Find the smallest number to the right of i that’s greater than nums[i], and swap them. 3. Reverse the subarray after i to get the smallest possible permutation from that point. If no such pair exists, reverse the entire array (smallest permutation).

Here’s a visual for [1,2,3]:

Step 1: [1,2,3] -> i = 1 (2 < 3)
Step 2: Swap 2 with 3 -> [1,3,2]
Step 3: Reverse after i=1 (already sorted) -> [1,3,2]

Find Pivot.

Scan right-to-left for nums[i] < nums[i+1].

Find Swap Candidate.

Find smallest number > nums[i] on the right.

Swap and Reverse.

Swap, then reverse subarray after i.

Handle Last Permutation.

If no pivot, reverse all to smallest.

Step-by-Step Example

Example 1: nums = [1,2,3]

We need [1,3,2].

Goal: Next permutation.
Result for Reference: [1,3,2].
Start: nums = [1,2,3].
Step 1: Find pivot, i = 1 (2 < 3), i = 0 (1 < 2, continue).
Step 2: From i = 1, find j > i where nums[j] > 2, j = 2 (3 > 2).
Step 3: Swap nums[1] = 2 with nums[2] = 3, nums = [1,3,2].
Step 4: Reverse after i = 1, [2] is single, nums = [1,3,2].
Finish: nums = [1,3,2].

Example 2: nums = [3,2,1]

We need [1,2,3].

Goal: Next permutation.
Result for Reference: [1,2,3].
Start: nums = [3,2,1].
Step 1: No i where nums[i] < nums[i+1] (3 > 2 > 1).
Step 2: Reverse entire array, nums = [1,2,3].
Finish: nums = [1,2,3].

How the Code Works (Optimal)

Here’s the Python code with line-by-line explanation:

def nextPermutation(nums: list[int]) -> None:
    # Line 1: Length of array
    n = len(nums)

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

    # Line 3: If i >= 0, find number to swap
    if i >= 0:
        j = n - 1
        # Line 4: Find smallest number > nums[i] on right
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        # Line 5: Swap
        nums[i], nums[j] = nums[j], nums[i]

    # Line 6: Reverse subarray after i
    left = i + 1
    right = n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Alternative: Generate-and-Find Approach

Explanation

Generate all permutations, find the current one, and return the next. This is impractical for LeetCode due to time and space but helps understand the concept.

Generate Permutations.
Sort Lexicographically.
Find Next.

Step-by-Step Example (Alternative)

For nums = [1,2,3]:

Goal: [1,3,2].
Step 1: Permutations = [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]].
Step 2: Current = [1,2,3], next = [1,3,2].
Finish: nums = [1,3,2].

How the Code Works (Alternative)

from itertools import permutations

def nextPermutationAlternative(nums: list[int]) -> None:
    # Line 1: Convert to tuple for comparison
    curr = tuple(nums)
    # Line 2: Generate all permutations
    perms = sorted(permutations(nums))
    # Line 3: Find current index
    idx = perms.index(curr)
    # Line 4: Next permutation or first if last
    next_idx = (idx + 1) % len(perms)
    # Line 5: Update nums in-place
    nums[:] = perms[next_idx]

Complexity

Optimal In-Place:

Time: O(n) – Single pass to find pivot, swap, and reverse.
Space: O(1) – In-place.

Generate-and-Find:

Time: O(n!) – Generating all permutations.
Space: O(n!) – Storing permutations.

Efficiency Notes

The in-place solution is O(n) and meets LeetCode’s requirements perfectly. The alternative is O(n!) and impractical but illustrates the permutation sequence.

Key Insights

Tips to master LeetCode 31:

Pivot is Key: Find where the sequence dips to increase it.
Reverse for Smallest: After swapping, minimize the tail.
In-Place Mastery: No extra arrays—manipulate directly!

Additional Example

For nums = [1,5,1]:

Goal: [5,1,1].
Optimal: i = 1 (1 < 5), swap 5 with 1, reverse [1], nums = [1,5,1].
Result: [1,5,1].

Edge Cases

Single Element: [1] – Remains [1].
Duplicates: [1,1] – Swap to [1,1].
Last Permutation: [2,1] – Reset to [1,2].

Final Thoughts

The Optimal In-Place solution is a gem for LeetCode 31 in Python—fast, elegant, and space-efficient. For a related challenge, explore LeetCode 30: Substring with Concatenation of All Words to tackle string permutations! Ready to test your skills? Solve LeetCode 31 on LeetCode now and play with arrays like [1,3,2] or [3,2,1] to see the magic unfold. Jump in and level up your permutation game!