Next Permutation

🎯

Next Permutation

mediumBACKTRACKINGAmazonGoogleFacebook

Imagine you have a list of numbers representing a password combination, and you want to find the next possible combination in lexicographical order to try next.

💡 This problem asks for the next lexicographically greater permutation of a sequence. Beginners often struggle because it requires understanding how permutations are ordered and how to manipulate the sequence in-place to get the next permutation without generating all permutations.

📋

Problem Statement

Given an array of integers nums representing a permutation, modify nums in-place to the next lexicographically greater permutation of numbers. If such arrangement is not possible, rearrange it as the lowest possible order (i.e., sorted in ascending order). The replacement must be in-place with only constant extra memory.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1,2,3]"

Output[1,3,2]

The next permutation after 1,2,3 is 1,3,2.

Input"[3,2,1]"

Output[1,2,3]

3,2,1 is the highest permutation, so we return the lowest permutation 1,2,3.

Input"[1,1,5]"

Output[1,5,1]

Next permutation after 1,1,5 is 1,5,1.

• Single element array [1] → output [1]
• All elements equal [2,2,2] → output [2,2,2]
• Strictly descending order [5,4,3,2,1] → output [1,2,3,4,5]
• Array with duplicates [1,3,2,3] → output [1,3,3,2]

⚠️

Common Mistakes

Not handling the case when the entire array is descending

Code fails to reset to lowest permutation, causing wrong output

✅ Add condition to reverse entire array if no pivot found

Swapping pivot with wrong element (not the smallest greater element)

Next permutation is incorrect or not lexicographically next

✅ Scan from right to find the first element greater than pivot to swap

Not reversing the suffix after swapping

Suffix remains in descending order, so permutation is not minimal next

✅ Reverse the suffix after pivot to get the smallest lex order suffix

Using extra space or generating all permutations

Solution is inefficient and may time out on large inputs

✅ Implement in-place approach with O(1) extra space

Incorrectly handling duplicates

Next permutation may skip valid permutations or produce duplicates

✅ Algorithm naturally handles duplicates by scanning and swapping correctly

🧠

Brute Force (Generate All Permutations and Find Next)

💡 This approach exists to build intuition by brute forcing all permutations and then finding the next one. It is impractical for large inputs but helps understand the problem deeply.

Intuition

Generate all permutations of the array, sort them lexicographically, then find the current permutation and return the next one in order.

Algorithm

1. Generate all permutations of the input array.
2. Sort all permutations lexicographically.
3. Find the index of the current permutation in the sorted list.
4. Return the permutation at the next index, or the first if current is last.

💡 This algorithm is conceptually simple but computationally expensive because generating all permutations grows factorially.

</>

Code

from itertools import permutations

def next_permutation(nums):
    perms = sorted(set(permutations(nums)))
    curr = tuple(nums)
    idx = perms.index(curr)
    next_idx = (idx + 1) % len(perms)
    nums[:] = perms[next_idx]

# Driver code
if __name__ == '__main__':
    arr = [1,2,3]
    next_permutation(arr)
    print(arr)  # Output: [1,3,2]

Line Notes

from itertools import permutationsImport permutations to generate all permutations easily

perms = sorted(set(permutations(nums)))Generate all unique permutations and sort them lex order

idx = perms.index(curr)Find the current permutation's index in the sorted list

nums[:] = perms[next_idx]Modify input array in-place to the next permutation

import java.util.*;

public class NextPermutationBrute {
    public static void nextPermutation(int[] nums) {
        List<List<Integer>> perms = new ArrayList<>();
        permute(nums, 0, perms);
        perms.sort((a,b) -> {
            for (int i = 0; i < a.size(); i++) {
                if (!a.get(i).equals(b.get(i))) return a.get(i) - b.get(i);
            }
            return 0;
        });
        List<Integer> curr = new ArrayList<>();
        for (int num : nums) curr.add(num);
        int idx = perms.indexOf(curr);
        List<Integer> next = perms.get((idx + 1) % perms.size());
        for (int i = 0; i < nums.length; i++) nums[i] = next.get(i);
    }

    private static void permute(int[] nums, int start, List<List<Integer>> perms) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) perm.add(num);
            if (!perms.contains(perm)) perms.add(perm);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, perms);
            swap(nums, start, i);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr)); // Output: [1,3,2]
    }
}

Line Notes

List<List<Integer>> perms = new ArrayList<>();Store all permutations generated

permute(nums, 0, perms);Generate all permutations recursively

perms.sort((a,b) -> {...});Sort permutations lex order using comparator

int idx = perms.indexOf(curr);Find current permutation index to get next

#include <bits/stdc++.h>
using namespace std;

void permute(vector<int>& nums, int start, vector<vector<int>>& perms) {
    if (start == (int)nums.size()) {
        perms.push_back(nums);
        return;
    }
    for (int i = start; i < (int)nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, perms);
        swap(nums[start], nums[i]);
    }
}

void nextPermutation(vector<int>& nums) {
    vector<vector<int>> perms;
    permute(nums, 0, perms);
    sort(perms.begin(), perms.end());
    auto it = find(perms.begin(), perms.end(), nums);
    int idx = distance(perms.begin(), it);
    nums = perms[(idx + 1) % perms.size()];
}

int main() {
    vector<int> arr = {1,2,3};
    nextPermutation(arr);
    for (int x : arr) cout << x << ' '; // Output: 1 3 2
    cout << '\n';
    return 0;
}

Line Notes

void permute(vector<int>& nums, int start, vector<vector<int>>& perms)Recursive function to generate all permutations

sort(perms.begin(), perms.end());Sort all permutations lexicographically

auto it = find(perms.begin(), perms.end(), nums);Find current permutation's position

nums = perms[(idx + 1) % perms.size()];Assign next permutation or wrap to first

function permute(nums, start, perms) {
    if (start === nums.length) {
        perms.push(nums.slice());
        return;
    }
    for (let i = start; i < nums.length; i++) {
        [nums[start], nums[i]] = [nums[i], nums[start]];
        permute(nums, start + 1, perms);
        [nums[start], nums[i]] = [nums[i], nums[start]];
    }
}

function nextPermutation(nums) {
    let perms = [];
    permute(nums, 0, perms);
    perms.sort((a,b) => {
        for (let i = 0; i < a.length; i++) {
            if (a[i] !== b[i]) return a[i] - b[i];
        }
        return 0;
    });
    let currStr = nums.join(',');
    let idx = perms.findIndex(p => p.join(',') === currStr);
    let next = perms[(idx + 1) % perms.length];
    for (let i = 0; i < nums.length; i++) nums[i] = next[i];
}

// Driver code
let arr = [1,2,3];
nextPermutation(arr);
console.log(arr); // Output: [1,3,2]

Line Notes

function permute(nums, start, perms)Recursive helper to generate permutations

perms.sort((a,b) => {...});Sort permutations lex order for indexing

let idx = perms.findIndex(p => p.join(',') === currStr);Find current permutation index

for (let i = 0; i < nums.length; i++) nums[i] = next[i];Overwrite input array in-place

⏱

Complexity

TimeO(n! * n log n) due to generating all permutations and sorting

SpaceO(n! * n) to store all permutations

Generating all permutations is factorial in n, sorting them adds n log n factor, and storing them requires large memory.

💡 For n=10, this means over 3 million permutations, which is impractical to compute or store.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and verify correctness on small inputs.

🧠

Better Approach (Find Pivot and Swap)

💡 This approach improves efficiency by directly finding the next permutation using a known pattern, avoiding generating all permutations.

Intuition

Traverse from the end to find the first decreasing element (pivot), then find the smallest element larger than pivot to the right, swap them, and reverse the suffix after pivot.

Algorithm

1. Scan from right to left to find the first index 'i' where nums[i] < nums[i+1].
2. If no such index exists, reverse the entire array and return.
3. Otherwise, scan from right to find the first index 'j' where nums[j] > nums[i].
4. Swap nums[i] and nums[j].
5. Reverse the subarray nums[i+1:] to get the next permutation.

💡 This algorithm cleverly uses the properties of permutations to find the next lexicographical order without generating all permutations.

</>

Code

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

# Driver code
if __name__ == '__main__':
    arr = [1,2,3]
    next_permutation(arr)
    print(arr)  # Output: [1,3,2]

Line Notes

i = len(nums) - 2Start from second last element to find pivot

while i >= 0 and nums[i] >= nums[i + 1]Find first decreasing element from right

if i >= 0:If pivot found, find element to swap with

while nums[j] <= nums[i]Find rightmost element greater than pivot

import java.util.*;

public class NextPermutationBetter {
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
    }

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr)); // Output: [1,3,2]
    }
}

Line Notes

int i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums, i + 1, nums.length - 1);Reverse suffix to get next permutation

#include <bits/stdc++.h>
using namespace std;

void nextPermutation(vector<int>& nums) {
    int i = (int)nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = (int)nums.size() - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> arr = {1,2,3};
    nextPermutation(arr);
    for (int x : arr) cout << x << ' '; // Output: 1 3 2
    cout << '\n';
    return 0;
}

Line Notes

int i = (int)nums.size() - 2;Start from second last element to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums.begin() + i + 1, nums.end());Reverse suffix to get next permutation

function nextPermutation(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}

// Driver code
let arr = [1,2,3];
nextPermutation(arr);
console.log(arr); // Output: [1,3,2]

Line Notes

let i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

while (left < right)Reverse suffix to get next permutation

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array from the end a few times and reverse a suffix in-place, all linear operations.

💡 For n=10^5, this means about 3 passes over the array, which is efficient and feasible.

Interview Verdict: Accepted

This is the optimal approach expected in interviews for this problem.

🧠

Space Optimized (In-place with Two Pointers and Reverse)

💡 This approach is the same as the better approach but emphasizes in-place operations and minimal extra space, which is critical for large inputs.

Intuition

By scanning from the right and swapping only necessary elements, then reversing the suffix in-place, we avoid extra memory and achieve optimal performance.

Algorithm

1. Find the pivot index from right where nums[i] < nums[i+1].
2. If pivot not found, reverse entire array and return.
3. Find the rightmost successor to pivot greater than nums[i].
4. Swap pivot and successor.
5. Reverse the suffix starting at pivot+1.

💡 The key is to reverse only the suffix after swapping to get the next permutation in-place.

</>

Code

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

# Driver code
if __name__ == '__main__':
    arr = [1,2,3]
    next_permutation(arr)
    print(arr)  # Output: [1,3,2]

Line Notes

i = len(nums) - 2Start from second last element to find pivot

while i >= 0 and nums[i] >= nums[i + 1]Find first decreasing element from right

if i >= 0:If pivot found, find element to swap with

while left < rightReverse suffix in-place to get next permutation

import java.util.*;

public class NextPermutationSpaceOpt {
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
    }

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr)); // Output: [1,3,2]
    }
}

Line Notes

int i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums, i + 1, nums.length - 1);Reverse suffix in-place to get next permutation

#include <bits/stdc++.h>
using namespace std;

void nextPermutation(vector<int>& nums) {
    int i = (int)nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = (int)nums.size() - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> arr = {1,2,3};
    nextPermutation(arr);
    for (int x : arr) cout << x << ' '; // Output: 1 3 2
    cout << '\n';
    return 0;
}

Line Notes

int i = (int)nums.size() - 2;Start from second last element to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums.begin() + i + 1, nums.end());Reverse suffix in-place to get next permutation

function nextPermutation(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}

// Driver code
let arr = [1,2,3];
nextPermutation(arr);
console.log(arr); // Output: [1,3,2]

Line Notes

let i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

while (left < right)Reverse suffix in-place to get next permutation

⏱

Complexity

TimeO(n)

SpaceO(1)

All operations are done in-place with linear scans and swaps.

💡 This approach is the most efficient and uses minimal memory, ideal for large inputs.

Interview Verdict: Accepted

This is the best practical approach to implement in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal in-place approach (Approach 2 or 3) is what you should code in 95% of interviews. Brute force is only for conceptual understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n log n)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Better Approach (Pivot and Swap)	O(n)	O(1)	No	N/A	Code this approach
3. Space Optimized (In-place Reverse)	O(n)	O(1)	No	N/A	Code this approach (same as 2)

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the better approach using pivot and suffix reversal.Step 4: Code the optimal in-place solution carefully.Step 5: Test with edge cases and explain time/space complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of permutation ordering, ability to optimize from brute force to linear time, and skill in in-place array manipulation.

Common Follow-ups

• How to find previous permutation? → Reverse the logic to find first increasing element from right.
• Can you do this for strings? → Yes, same logic applies to character arrays.

💡 These follow-ups test your ability to adapt the core logic to variations and different data types.

🔍

Pattern Recognition

When to Use

1) Asked for next or previous lexicographical permutation; 2) Input is a sequence or array; 3) Need in-place or efficient solution; 4) Problem involves rearranging elements to next order.

Signature Phrases

next lexicographically greater permutationrearrange to next orderin-place modification

NOT This Pattern When

Generating all permutations without order constraints or problems requiring all permutations explicitly

Similar Problems

Permutation Sequence - find kth permutation using factorial number systemPrevious Permutation - find previous lexicographical permutationNext Greater Element III - next permutation of digits in a number