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

Practice

1. Consider the following bitmask-based backtracking code for n=4. After placing the first queen at row 0, column 1, what is the value of available_positions at row 1 (second recursive call)?

easy

A. 0b1010 (binary 10 decimal)

B. 0b1100 (binary 12 decimal)

C. 0b1001 (binary 9 decimal)

D. 0b1000 (binary 8 decimal)

Solution

1. Step 1: Trace first queen placement at row 0, col 1

   Position bitmask = 0b0010 (decimal 2). Update cols=0b0010, diag1=(0b0010)<<1=0b0100, diag2=(0b0010)>>1=0b0001.

2. Step 2: Compute available_positions at row 1

   available_positions = (0b1111) & ~(cols | diag1 | diag2) = 0b1111 & ~(0b0010 | 0b0100 | 0b0001) = 0b1111 & ~0b0111 = 0b1111 & 0b1000 = 0b1000 (decimal 8). The only available position is column 3 (bit 3).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask after first queen excludes cols 1, diag1 shifted left, diag2 shifted right [OK]

Hint: Bitmask tracks attacked columns and diagonals precisely [OK]

Common Mistakes:

• Miscomputing diagonal shifts
• Off-by-one in bit length
• Confusing cols with diag masks

2. You are given a string containing only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

3. Consider the following code snippet implementing the optimal backtracking solution for Word Search. Given the board = [["A","B","C"],["D","E","F"],["G","H","I"]] and word = "BEF", what is the return value of exist(board, word)?

easy

A. True

B. False

C. Raises IndexError

D. Infinite recursion

Solution

1. Step 1: Trace dfs starting at cell (0,1) 'B'

   Word starts with 'B', found at (0,1). dfs(0,1,0) matches 'B'.

2. Step 2: Explore neighbors for next chars 'E' and 'F'

   From (0,1), neighbors checked: (1,1) 'E' matches next char, then (1,2) 'F' matches last char. All matched, return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All characters found sequentially with valid moves [OK]

Hint: Trace dfs calls carefully to confirm path exists [OK]

Common Mistakes:

• Assuming no path due to adjacency confusion
• Missing in-place marking effect

4. What is the time complexity of the backtracking with bitmask optimization approach for counting beautiful arrangements of size n?

medium

A. O(n * n!)

B. O(n^2)

C. O(n * 2^n)

D. O(n!)

Solution

1. Step 1: Identify the search space

   The algorithm explores permutations of n numbers, which is n! in worst case.

2. Step 2: Consider pruning and bitmask usage

   Bitmask helps track used numbers efficiently, pruning invalid branches but the total number of recursive calls is proportional to n * n! because for each position, up to n choices are tried.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores permutations with n choices per position, leading to O(n * n!) complexity [OK]

Hint: Backtracking permutations with bitmask -> O(n * n!) time [OK]

Common Mistakes:

• Confusing bitmask with exponential 2^n complexity
• Assuming polynomial due to pruning

5. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.

medium

A. O(M * N * 4 * 3^(L-1)) due to pruning and adjacency constraints

B. O(M * N * 4^L * W), where W is the number of words

C. O(M * N * L^2) because each cell explores all prefixes

D. O(M * N * L) since each cell is visited once per character

Solution

1. Step 1: Identify branching factor in backtracking

   From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.

2. Step 2: Calculate complexity with pruning

   Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known complexity from Trie + backtracking analysis [OK]

Hint: Branching factor reduces after first step due to visited constraints [OK]

Common Mistakes:

• Confusing W (number of words) as multiplicative factor in optimal approach.