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
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 100
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
- Scan from the right for the first index i where a[i] < a[i+1] — everything after i is in decreasing order.
- 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);
}
}