Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Next Permutation

MEDIUMProblemSolveExternal Links

Description

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such an arrangement is not possible (the array is in descending order — the last permutation), it must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of [1, 2, 3] is [1, 3, 2], and the next permutation of [3, 2, 1] is [1, 2, 3].

The replacement must be in place and use only constant extra memory.

Examples

Example 1

Input: nums = [1, 2, 3]

Output: [1, 3, 2]

Explanation: The permutations of [1, 2, 3] in lexicographic order are: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation after [1,2,3] is [1,3,2].

Example 2

Input: nums = [3, 2, 1]

Output: [1, 2, 3]

Explanation: [3, 2, 1] is the last permutation in lexicographic order, so the next permutation wraps around to the first: [1, 2, 3].

Example 3

Input: nums = [1, 1, 5]

Output: [1, 5, 1]

Explanation: Treating duplicate values correctly, the next permutation after [1, 1, 5] is [1, 5, 1]. The element 5 moves left past the second 1.

Constraints

  • 1 ≤ nums.length ≤ 100
  • 0 ≤ nums[i] ≤ 100

Editorial

Brute Force

Intuition

The most straightforward approach is to generate all permutations of the given array, sort them in lexicographic order, find the current permutation in that sorted list, and return the one that comes right after it. If the current permutation is the last one, we wrap around to the first.

Imagine you have a dictionary of all possible words you can form from a set of letters. To find the "next word," you just look it up in the dictionary and read the entry that follows.

While conceptually simple, this is extremely expensive. For an array of length n, there are n! permutations. Generating, sorting, and searching through them takes factorial time, making it impractical for anything beyond tiny arrays.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3]:

Step 1: Generate all permutations of [1, 2, 3]:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

Step 2: Sort them lexicographically (they are already sorted above).

Step 3: Find [1, 2, 3] in the list — it's at index 0.

Step 4: The next permutation is at index 1: [1, 3, 2].

Step 5: Return [1, 3, 2].

For nums = [3, 2, 1]: it's at index 5 (the last one), so we wrap to index 0 → [1, 2, 3].

Brute Force — Generate All Permutations — Watch as we generate all permutations, sort them, locate the current one, and pick the next entry.

Algorithm

  1. Generate all permutations of the input array
  2. Sort all permutations in lexicographic order
  3. Find the current permutation in the sorted list
  4. If it's the last permutation, return the first one (wrap around)
  5. Otherwise, return the next permutation in the sorted list
  6. Copy the result back into the input array (in-place)

Code

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

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        vector<vector<int>> perms;
        vector<int> sorted_nums = nums;
        sort(sorted_nums.begin(), sorted_nums.end());
        
        // Generate all permutations
        do {
            perms.push_back(sorted_nums);
        } while (next_permutation(sorted_nums.begin(), sorted_nums.end()));
        
        // Find current and get next
        for (int i = 0; i < perms.size(); i++) {
            if (perms[i] == nums) {
                if (i == perms.size() - 1) {
                    nums = perms[0];
                } else {
                    nums = perms[i + 1];
                }
                return;
            }
        }
    }
};
from itertools import permutations

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        # Generate all unique permutations sorted lexicographically
        all_perms = sorted(set(permutations(nums)))
        
        current = tuple(nums)
        idx = all_perms.index(current)
        
        # Get next permutation (wrap around if at end)
        next_perm = all_perms[(idx + 1) % len(all_perms)]
        
        for i in range(len(nums)):
            nums[i] = next_perm[i]
import java.util.*;

class Solution {
    public void nextPermutation(int[] nums) {
        List<int[]> perms = new ArrayList<>();
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        
        // Generate all permutations
        generatePerms(sorted, 0, perms);
        perms.sort((a, b) -> {
            for (int i = 0; i < a.length; i++) {
                if (a[i] != b[i]) return a[i] - b[i];
            }
            return 0;
        });
        
        // Find current and get next
        for (int i = 0; i < perms.size(); i++) {
            if (Arrays.equals(perms.get(i), nums)) {
                int nextIdx = (i + 1) % perms.size();
                System.arraycopy(perms.get(nextIdx), 0, nums, 0, nums.length);
                return;
            }
        }
    }
    
    private void generatePerms(int[] arr, int start, List<int[]> result) {
        if (start == arr.length) {
            result.add(arr.clone());
            return;
        }
        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);
            generatePerms(arr, start + 1, result);
            swap(arr, start, i);
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Complexity Analysis

Time Complexity: O(n! × n)

Generating all permutations takes O(n!). Sorting them lexicographically takes O(n! × n log(n!)). Searching for the current permutation takes O(n! × n). Overall: O(n! × n).

Space Complexity: O(n! × n)

We store all n! permutations, each of length n. This requires O(n! × n) space.

Why This Approach Is Not Efficient

The brute force approach has factorial time and space complexity, which is catastrophic. For n = 100 (the maximum constraint), 100! is an astronomically large number — far more than the number of atoms in the observable universe. Even for n = 15, 15! ≈ 1.3 trillion permutations.

Moreover, the problem explicitly requires constant extra memory, which the brute force violates by storing all permutations.

The fundamental issue is that the brute force treats this as a "search" problem, when it's actually a pattern recognition problem. The next permutation can be constructed directly from the current one by identifying the right digit to change and making a minimal adjustment.

The key insight: look at the array from the right. If the suffix is entirely in decreasing order, no rearrangement of just the suffix can produce a larger permutation — we need to involve a digit from further left. We find the rightmost position where the sequence starts to decrease (looking right-to-left), make a minimal swap, and sort the remaining suffix. This runs in O(n) time and O(1) space.

Optimal Approach - Find Pivot and Rearrange

Intuition

Think of the array as a number. To get the next larger number using the same digits, you want to make the smallest possible increase.

Consider the number 1 5 8 4 7 6 5 3 1:

  1. Find the rightmost ascent (the pivot): Scan from right to left looking for the first index where nums[i] < nums[i + 1]. Everything to the right of this index is in non-increasing order — no rearrangement of just that suffix can yield something larger. The element at index i is the "pivot" — the digit we need to increase.

    In our example: scanning from right → 1 ≥ 3? No... 3 ≥ 5? No... 5 ≥ 6? No... 6 ≥ 7? No... 7 ≥ 4? Yes, so 4 at index 3 is the pivot (since nums[3] = 4 < nums[4] = 7).

  2. Find the smallest element larger than the pivot (from the right): In the suffix to the right of the pivot, find the rightmost element that is larger than the pivot. Swapping with the rightmost such element ensures we make the smallest increase to the pivot position.

    Suffix [7, 6, 5, 3, 1]: the rightmost element > 4 is 5 at index 6.

  3. Swap the pivot with that element: After swapping, the suffix is still in non-increasing order (a critical property).

    After swap: 1 5 8 5 7 6 4 3 1

  4. Reverse the suffix: Since the suffix is in non-increasing order, reversing it gives the smallest possible arrangement of those digits — making the overall number as small as possible while still being larger than the original.

    Reverse suffix after index 3: 1 5 8 5 1 3 4 6 7

Result: 1 5 8 5 1 3 4 6 7 — the next permutation!

If no pivot is found (the entire array is non-increasing), the array is the last permutation, so we simply reverse it to get the first permutation.

Step-by-Step Explanation

Let's trace with nums = [2, 3, 6, 5, 4, 1]:

Step 1 – Find the pivot: Scan right to left.

  • Index 4: nums[4]=4 vs nums[5]=1 → 4 > 1, continue
  • Index 3: nums[3]=5 vs nums[4]=4 → 5 > 4, continue
  • Index 2: nums[2]=6 vs nums[3]=5 → 6 > 5, continue
  • Index 1: nums[1]=3 vs nums[2]=6 → 3 < 6 ✓ → pivot = index 1 (value 3)

Step 2 – Find swap target: In suffix [6, 5, 4, 1], find rightmost element > 3.

  • Index 5: nums[5]=1 → 1 > 3? No
  • Index 4: nums[4]=4 → 4 > 3? Yes → swap target = index 4 (value 4)

Step 3 – Swap: Swap nums[1] and nums[4].
Array becomes: [2, 4, 6, 5, 3, 1]

Step 4 – Reverse suffix: Reverse from index 2 to end.
[2, 4, 6, 5, 3, 1] → [2, 4, 1, 3, 5, 6]

Result: [2, 4, 1, 3, 5, 6]

Next Permutation — Find Pivot and Rearrange — Watch the three-phase algorithm: find the pivot, swap with the smallest larger element, and reverse the suffix to get the next permutation in O(n) time.

Algorithm

  1. Find the pivot: Start from the rightmost element. Scan left to find the first index i where nums[i] < nums[i + 1]. If no such index exists, the array is the last permutation — go to step 4.

  2. Find the swap target: From the right end, find the first index j where nums[j] > nums[i]. This is the smallest element in the suffix that is larger than the pivot.

  3. Swap: Swap nums[i] and nums[j].

  4. Reverse the suffix: Reverse the sub-array from nums[i + 1] to the end. If no pivot was found (step 1), reverse the entire array.

Code

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

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 2;
        
        // Step 1: Find the pivot
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            // Step 2: Find the swap target
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // Step 3: Swap
            swap(nums[i], nums[j]);
        }
        
        // Step 4: Reverse the suffix
        reverse(nums.begin() + i + 1, nums.end());
    }
};
class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        n = len(nums)
        i = n - 2
        
        # Step 1: Find the pivot
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        if i >= 0:
            # Step 2: Find the swap target
            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
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        
        // Step 1: Find the pivot
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            // Step 2: Find the swap target
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // Step 3: Swap
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        // Step 4: Reverse the suffix
        int left = i + 1, right = n - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Finding the pivot scans at most n-1 elements from right to left: O(n). Finding the swap target scans the suffix: O(n) in the worst case. Reversing the suffix: O(n). Total: O(n).

Space Complexity: O(1)

All operations are performed in-place using only a constant number of variables (i, j, left, right, temp). No additional arrays or data structures are needed. This satisfies the problem's requirement of constant extra memory.