Next Permutation

Medium
185.

Next Permutation

Next Permutation is a medium coding problem on arrays and two pointers, asked in Amazon, Google, Microsoft and Meta interviews.

A permutation of an array is one of its possible orderings. Listing all permutations of an array in increasing lexicographic order gives a sequence; the next permutation of an arrangement is the one that follows it in that sequence.

If no greater arrangement exists, the next permutation is the smallest one — the array sorted in ascending order.

Given nums, return its next permutation.

Example 1

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

Example 2

Input
nums = [3,2,1]
Output
[1,2,3]
Explanation
This is the largest arrangement, so it wraps to the smallest.

Example 3

Input
nums = [1,1,5]
Output
[1,5,1]

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 30
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextPermutation = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Next Permutation — Solution in Python, Java & C++

Next Permutation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Next Permutation is a medium coding problem on arrays and two pointers, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

A permutation of an array is one of its possible orderings. Listing all permutations of an array in increasing lexicographic order gives a sequence; the next permutation of an arrangement is the one that follows it in that sequence.

If no greater arrangement exists, the next permutation is the smallest one — the array sorted in ascending order.

Given nums, return its next permutation.

Example 1

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

Example 2

Input: nums = [3,2,1]
Output: [1,2,3]
Explanation: This is the largest arrangement, so it wraps to the smallest.

Example 3

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 30

Hints for Next Permutation

  1. Hint 1

    Scan from the right for the first index i with nums[i] < nums[i + 1] — the suffix after it is non-increasing and already maximal.

  2. Hint 2

    Swap nums[i] with the rightmost element greater than it; that is the smallest possible increase at position i.

  3. Hint 3

    Then reverse the suffix, turning the largest arrangement of those values into the smallest.

How to solve Next Permutation

Find the rightmost position that can still be increased, raise it by the smallest possible amount, then make the suffix after it as small as possible.

Approach

  1. Scan from the right for the first i with nums[i] < nums[i + 1]; the suffix after i is non-increasing.
  2. If such i exists, find the rightmost j > i with nums[j] > nums[i] and swap them.
  3. Reverse the suffix starting at i + 1.

Why it works

The suffix after i is the largest arrangement of its elements, so no larger permutation shares the prefix through i. Swapping in the smallest larger value at i gives the least possible increase there, and the suffix stays non-increasing, so reversing it yields the smallest completion. When no i exists the array is the last permutation and reversing everything wraps to the first.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The comparisons must be >= / <= when scanning so equal elements are skipped correctly.
  • Forgetting the reverse produces a larger permutation, not the next one.

Reference solution

Python

def nextPermutation(nums):
    nums = list(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]
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Java

public static int[] nextPermutation(int[] nums) {
    int[] a = Arrays.copyOf(nums, nums.length);
    int n = a.length;
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    for (int l = i + 1, r = n - 1; l < r; l++, r--) {
        int t = a[l]; a[l] = a[r]; a[r] = t;
    }
    return a;
}

C++

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

JavaScript

var nextPermutation = function(nums) {
    const a = nums.slice();
    const n = a.length;
    let i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i >= 0) {
        let j = n - 1;
        while (a[j] <= a[i]) j--;
        const t = a[i]; a[i] = a[j]; a[j] = t;
    }
    for (let l = i + 1, r = n - 1; l < r; l++, r--) {
        const t = a[l]; a[l] = a[r]; a[r] = t;
    }
    return a;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique