Next Permutation Explained Step by Step

Introduction

In many problems, we need to rearrange numbers into the next possible greater order. This is known as the next permutation.

This problem is important because it teaches how to manipulate arrays efficiently without generating all permutations.

Problem Statement

Given an array of integers nums, rearrange it into the next lexicographically greater permutation.

If such an arrangement is not possible, rearrange it into the lowest possible order (ascending order).

The rearrangement must be done in-place using constant extra memory.

Example 1:

Input:

nums = [1, 2, 3]

Output:

[1, 3, 2]

Example 2:

Input:

nums = [3, 2, 1]

Output:

[1, 2, 3]

Explanation:
This is the last permutation, so we return the smallest.

Understanding the Idea

The goal is to find the next greater arrangement of numbers.

Instead of generating all permutations, we follow a pattern.

Step-by-Step Approach

Step 1: Find the breakpoint

Traverse from right to left and find the first index i such that:

nums[i] < nums[i + 1]

Step 2: Find the next greater element

Again traverse from the right and find an element just greater than nums[i].

Step 3: Swap

Swap these two elements.

Step 4: Reverse the remaining array

Reverse the part of the array after index i to get the smallest order.

Python Implementation

def next_permutation(nums):
    n = len(nums)

    # Step 1: Find breakpoint
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: Find next greater element
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1

        # Step 3: Swap
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: Reverse remaining part
    nums[i + 1:] = reversed(nums[i + 1:])

    return nums

# Example usage
nums = [1, 2, 3]
print(next_permutation(nums))

Step-by-Step Example

For:

[1, 2, 3]

• Breakpoint at index 1 (2 < 3)
• Swap 2 and 3 → [1, 3, 2]
• Reverse after index → no change

Result: [1, 3, 2]

Key Points

• Works in-place
• No need to generate all permutations
• Uses simple traversal and swapping
• Very common interview question

Conclusion

The Next Permutation problem is a great example of how understanding patterns can lead to efficient solutions. Instead of brute force, we use a step-by-step approach to find the next arrangement in linear time.

Mastering this concept helps in solving many permutation and array-based problems.