Next Permutation

Introduction

A permutation of an array is simply a rearrangement of its elements.
The next permutation refers to the next lexicographically greater arrangement of numbers.

If no such arrangement exists (i.e., the array is in descending order), we rearrange it to the smallest possible order (ascending).

Problem Statement

Given an integer array nums, find the next permutation of the array.

Conditions:

• Modify the array in-place
• Use only constant extra space

Examples

Example 1:
Input: [1, 2, 3]
Output: [1, 3, 2]

Example 2:
Input: [3, 2, 1]
Output: [1, 2, 3]

Example 3:
Input: [1, 1, 5]
Output: [1, 5, 1]

Intuition

To get the next permutation:

• We need to make a slightly larger arrangement
• Change the number from the rightmost side

Approach

Steps

• Find the first decreasing element (pivot)

  • Traverse from right
  • Find index i such that nums[i] < nums[i+1]

• Find the next greater element

  • From right, find element just greater than nums[i]

• Swap them

• Reverse the remaining array (right side)

  • This gives the smallest possible order

Code (Python)

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

    # Step 1: Find pivot
    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 the suffix
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Step-by-Step Explanation

For [1, 2, 3]:

• Pivot = 2
• Next greater = 3
• Swap → [1, 3, 2]
• Reverse right → already smallest

For [3, 2, 1]:

• No pivot found
• Reverse entire array → [1, 2, 3]

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Conclusion

The Next Permutation problem is a classic example of greedy + array manipulation.
Understanding this helps in solving many permutation-based problems efficiently.