Next Permutation

Next Permutation trips up a lot of people. The idea sounds simple. Find the next bigger arrangement of the same numbers. But the clean solution is a precise dance of three small steps. This question tests whether you can spot a pattern and turn it into exact code.

🎯 The Problem

You get an array of numbers and you want the next bigger arrangement of those same numbers. An arrangement of the same numbers is called a permutation. Here are the rules.

• List all arrangements from smallest to largest, then return the one right after the current one.
• If the current one is already the largest, wrap around to the smallest.
• You must change the array in place. So you cannot build a big new list. You only swap and reverse inside the array you were given.

Let us say the array is [1, 2, 3]. The next bigger arrangement is [1, 3, 2]. For [3, 2, 1], which is already the largest, you wrap around to [1, 2, 3].

Input:  nums = [1, 2, 3]
Output: [1, 3, 2]

Explanation: [1, 3, 2] is the smallest arrangement that is larger than [1, 2, 3]

Here is a picture of what “next” means. The arrangements sit in order from small to large. We want the one right after the current one.

🐢 Approach 1: Generate All Permutations (Brute Force)

The idea in one line: build every arrangement, sort them, then return the one after the current.

The idea:

• List every permutation of the numbers.
• Sort that list from smallest to largest.
• Find the current arrangement and return the next one.

Why it is weak:

• For n numbers there are n factorial arrangements.
• So this is O(n!) time. Far too slow past tiny arrays.
• It also holds every arrangement in memory, so it is heavy on space.

Here is the brute-force idea as code:

from itertools import permutations


def next_permutation(nums):
    all_orders = sorted(set(permutations(nums)))
    current = tuple(nums)
    index = all_orders.index(current)

    if index == len(all_orders) - 1:
        nums[:] = list(all_orders[0])
    else:
        nums[:] = list(all_orders[index + 1])


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

⚡ Approach 2: Pivot, Swap, Reverse (Best)

The idea in one line: bump the rightmost spot that can grow, then make the tail as small as possible.

Find the pivot:

• Scan from the right for the first index i where nums[i] < nums[i + 1].
• That spot is the pivot, the number we bump up.
• The tail to the right of the pivot is already in falling order, so it is the largest that tail can be.
• No pivot means the whole array is the largest. Then just reverse it to get the smallest.

Swap the pivot up:

• Scan from the right again.
• Find the smallest value still bigger than the pivot.
• Swap those two. Now the pivot spot holds the next bigger value it can take.

Reverse the tail:

• The tail after the pivot is still in falling order.
• Reverse it into rising order.
• That gives the smallest ending after the bump.

Why it is fast:

• A few passes from the right and one reverse.
• Each element is touched a constant number of times.
• So it runs in O(n) time and uses no extra array.

This picture shows the three steps on [1, 2, 3]. Follow the pivot, the swap, then the reverse.

Steps to Solve

1. Walk from the right and find the first index i where nums[i] < nums[i + 1]. Call i the pivot.
2. If no such pivot exists, reverse the whole array and stop.
3. Walk from the right and find the first index j where nums[j] > nums[i].
4. Swap nums[i] and nums[j].
5. Reverse the part of the array after index i to put the tail in rising order.

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

void reverse(int nums[], int lo, int hi) {
    while (lo < hi) {
        swap(&nums[lo], &nums[hi]);
        lo++; hi--;
    }
}

void nextPermutation(int nums[], int n) {
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {  // find the pivot
        i--;
    }
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) {            // find just-bigger value
            j--;
        }
        swap(&nums[i], &nums[j]);               // bump the pivot up
    }
    reverse(nums, i + 1, n - 1);                // make the tail smallest
}

int main(void) {
    int nums[] = {1, 2, 3};
    int n = 3;
    nextPermutation(nums, n);
    printf("[");
    for (int k = 0; k < n; k++) {
        printf("%d", nums[k]);
        if (k < n - 1) printf(", ");
    }
    printf("]\n");
    return 0;
}

[1, 3, 2]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void nextPermutation(vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {  // find the pivot
        i--;
    }
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) {            // find just-bigger value
            j--;
        }
        swap(nums[i], nums[j]);                 // bump the pivot up
    }
    reverse(nums.begin() + i + 1, nums.end());  // make the tail smallest
}

int main() {
    vector<int> nums = {1, 2, 3};
    nextPermutation(nums);
    cout << "[";
    for (int k = 0; k < (int)nums.size(); k++) {
        cout << nums[k];
        if (k < (int)nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[1, 3, 2]

import java.util.Arrays;

public class NextPermutation {
    static void swap(int[] nums, int a, int b) {
        int t = nums[a]; nums[a] = nums[b]; nums[b] = t;
    }

    static void reverse(int[] nums, int lo, int hi) {
        while (lo < hi) {
            swap(nums, lo, hi);
            lo++; hi--;
        }
    }

    public static void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {  // find the pivot
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {            // find just-bigger value
                j--;
            }
            swap(nums, i, j);                        // bump the pivot up
        }
        reverse(nums, i + 1, n - 1);                // make the tail smallest
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3 };
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}

[1, 3, 2]

def next_permutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:   # find the pivot
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:              # find just-bigger value
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]    # bump the pivot up
    # reverse the tail after the pivot to make it smallest
    nums[i + 1:] = reversed(nums[i + 1:])


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

[1, 3, 2]

function nextPermutation(nums) {
  const n = nums.length;
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {   // find the pivot
    i--;
  }
  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) {               // find just-bigger value
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];   // bump the pivot up
  }
  // reverse the tail after the pivot to make it smallest
  let lo = i + 1, hi = n - 1;
  while (lo < hi) {
    [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
    lo++; hi--;
  }
}

const nums = [1, 2, 3];
nextPermutation(nums);
console.log(nums);

[ 1, 3, 2 ]

Let us walk through the Python version line by line. Code first, then the why.

def next_permutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])

i = n - 2 starts the search one step from the right end. We compare each element with the one after it. So we never need to look past the last index.

while i >= 0 and nums[i] >= nums[i + 1]: walks left until the order stops rising. The first place where a number is smaller than its right neighbor is the pivot. If we walk all the way off the left edge, i becomes -1, which means no pivot exists.

if i >= 0: runs only when we found a pivot. If there was no pivot, we skip straight to the reverse, which turns the largest arrangement back into the smallest.

while nums[j] <= nums[i]: finds the smallest value on the right that is still bigger than the pivot. The tail is in falling order, so the first value from the right that beats the pivot is exactly the one we want.

nums[i], nums[j] = nums[j], nums[i] swaps them. Now the pivot position holds the next allowed bigger value.

nums[i + 1:] = reversed(nums[i + 1:]) reverses the tail. The tail was in falling order, so reversing it makes it rise. That gives the smallest possible ending after the bump, which is exactly the next permutation.

⏱️ Time and Space Complexity

The brute force builds every arrangement, so it is hopelessly slow and memory heavy. The pivot method makes a few passes from the right and one reverse, so it touches each element a constant number of times. That gives O(n) time and no extra array, which is O(1) space.

🧩 Key Takeaways

• ✅ The next permutation is the smallest arrangement that is still bigger than the current one.
• ✅ Find the pivot, which is the first drop scanning from the right.
• ✅ Swap the pivot with the smallest value to its right that is still bigger.
• ✅ Reverse the tail after the pivot to make the ending as small as possible.
• ✅ If there is no pivot, the array is the largest, so reverse the whole thing to get the smallest.

🚀 What’s Next?

• Plus One
• Subarray Sum Equals K