Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Next Permutation

Medium · Arrays · Asked at Amazon, Google, Microsoft, Adobe, Uber

Rearrange the numbers into the next lexicographically greater permutation. If the array is already the largest permutation, rearrange it into the smallest one (sorted ascending).

Input

First line: n. Second line: n space-separated integers.

Output

The next permutation, space-separated.

Constraints

From the right, find the first i with a[i] < a[i+1]. Swap a[i] with the smallest larger element to its right, then reverse the suffix after i.

Example 1

Input

3
1 2 3

Output

1 3 2

Example 2

Input

3
3 2 1

Output

1 2 3

Hints

  1. Scan from the right for the first index i where a[i] < a[i+1] — everything after i is in decreasing order.
  2. Swap a[i] with the rightmost element greater than it, then reverse the part after i. If no such i exists, just reverse the whole array.

Approach

The suffix after the "pivot" i is the largest possible arrangement of those numbers, so to get the next permutation we must increase a[i] by the smallest possible amount: swap it with the smallest element in the suffix that is still larger (scanning from the right finds it, because the suffix is decreasing). After the swap the suffix is still decreasing — reverse it to make it the smallest. If there is no pivot, the array is the last permutation and reversing it gives the first.

Complexity: O(n) time · O(1) space

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    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());
    for (int k = 0; k < n; k++) cout << a[k] << (k + 1 < n ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
i = n - 2
while i >= 0 and a[i] >= a[i + 1]:
    i -= 1
if i >= 0:
    j = n - 1
    while a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]
a[i + 1 :] = reversed(a[i + 1 :])
print(*a)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int k = 0; k < n; k++) a[k] = sc.nextInt();
        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;
        }
        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < n; k++) sb.append(a[k]).append(k + 1 < n ? " " : "");
        System.out.println(sb);
    }
}

Solve Next Permutation online · All practice problems