Given an integer array nums of length n, where the current order represents one permutation of its values. Values may repeat, and lexicographic order is compared from left to right. Rearrange nums in-place into the next greater permutation.
If no greater permutation exists, rearrange nums into the smallest possible order.
Example 1
Input: nums = [2, 1, 5, 4, 3, 0, 0]
Output: [2, 3, 0, 0, 1, 4, 5]
Explanation: The suffix [5, 4, 3, 0, 0] is already in non-increasing order, so the first possible increase is made at value 1. It is swapped with 3, and the suffix is rearranged into ascending order.
Example 2
Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Explanation: The array is already the largest lexicographic permutation. Therefore, it is rearranged into the smallest order.
Brute Force Approach
All possible arrangements of the array can be generated and placed in lexicographic order. Once the current arrangement is located, the next arrangement in that sorted list is the answer.
If the current arrangement is the last one, the first arrangement in the sorted list is the smallest permutation. This method follows the definition directly, but it becomes impractical as n grows because the number of arrangements grows factorially.
Algorithm
Generate every arrangement by recursively choosing unused positions from the original array.
Store a copy whenever an arrangement reaches length
n, then return from that recursive path.Sort all generated arrangements in lexicographic order.
Find the first arrangement that is lexicographically greater than the original array and copy it into nums.
If no greater arrangement exists, copy the first sorted arrangement into nums.
Dry Run
Brute Force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Stores every permutation formed from the original positions. void generatePermutations(vector<int>& nums, vector<int>& current, vector<bool>& used, vector<vector<int>>& permutations) { int n = nums.size(); // A complete arrangement is ready to be stored. if (current.size() == nums.size()) { permutations.push_back(current); return; } // Try every unused original position as the next choice. for (int index = 0; index < n; index++) { // Used positions cannot be selected again in the same arrangement. if (used[index]) { continue; } used[index] = true; current.push_back(nums[index]); generatePermutations(nums, current, used, permutations); current.pop_back(); used[index] = false; } }public: // Rearranges nums into the next lexicographic permutation. void nextPermutation(vector<int>& nums) { int n = nums.size(); // A single value cannot move to a different permutation. if (n <= 1) { return; } vector<int> original = nums; vector<int> current; vector<bool> used(n, false); vector<vector<int>> permutations; generatePermutations(nums, current, used, permutations); // Put every generated arrangement in lexicographic order. sort(permutations.begin(), permutations.end()); // Choose the first arrangement strictly greater than the original. for (int index = 0; index < permutations.size(); index++) { // The first greater arrangement is the next permutation. if (permutations[index] > original) { nums = permutations[index]; return; } } nums = permutations[0]; }};// Driver codeint main() { vector<int> nums = {2, 1, 5, 4, 3, 0, 0}; // instance for class Solution Solution sol; sol.nextPermutation(nums); // Print the array after in-place rearrangement. for (int value : nums) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n! * n log(n!)), because n! generated arrangements may be sorted and each lexicographic comparison can inspect up to n values.
Space Complexity: O(n! * n), because all generated arrangements are stored and each arrangement contains n values.
Better Approach
Instead of generating every arrangement, the next permutation can be built by changing the rightmost position where a larger value can still be placed. A position can be increased only when a greater value exists somewhere to its right.
The longest suffix that is already in non-increasing order cannot be improved internally. The position just before that suffix is the best place to make the smallest possible increase. After that increase, sorting the suffix in ascending order gives the smallest sequence that follows it.
Algorithm
Move from right to left to find the first position whose value is smaller than the value immediately after it.
If no such position exists, sort the full array in ascending order and stop.
In the suffix to the right, find the smallest value greater than the chosen position's value.
Swap those two values to make the smallest possible increase at the rightmost useful position.
Sort the suffix in ascending order, then stop because the array now represents the next permutation.
Dry Run
Better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Rearranges nums into the next lexicographic permutation. void nextPermutation(vector<int>& nums) { int n = nums.size(); // A single value cannot move to a different permutation. if (n <= 1) { return; } int pivot = n - 2; // Search for the rightmost position that can be increased. while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) { pivot--; } // A fully non-increasing array has no greater permutation. if (pivot < 0) { sort(nums.begin(), nums.end()); return; } int successor = pivot + 1; // Find the smallest suffix value greater than the pivot value. for (int index = pivot + 1; index < n; index++) { // A better successor is greater than the pivot but smaller than the current successor. if (nums[index] > nums[pivot] && nums[index] <= nums[successor]) { successor = index; } } swap(nums[pivot], nums[successor]); // Minimize the suffix after the pivot has been increased. sort(nums.begin() + pivot + 1, nums.end()); }};// Driver codeint main() { vector<int> nums = {2, 1, 5, 4, 3, 0, 0}; // instance for class Solution Solution sol; sol.nextPermutation(nums); // Print the array after in-place rearrangement. for (int value : nums) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n log n), because the suffix or the whole array may be sorted after a linear pivot search.
Space Complexity: O(1) auxiliary space apart from implementation-dependent sorting overhead.
Optimal Approach
Instead of sorting the suffix, the optimal method first decides where the smallest possible increase can happen. In lexicographic order, earlier positions matter more than later positions. Therefore, the next permutation should keep the left side unchanged for as long as possible and increase the array at the farthest-right valid position.
The search starts from the end for that reason. As long as each value is greater than or equal to the value after it, that part is non-increasing. A non-increasing suffix is already the largest arrangement of those values, so rearranging only that suffix cannot create a greater permutation. The first position whose value is smaller than the value immediately after it is the pivot, because a larger value definitely exists on its right.
If no such increase point exists, the whole array is already in non-increasing order. That means it is the last possible lexicographic permutation. Since the problem asks to wrap around in that case, reversing the whole array gives the smallest permutation, which is the ascending order of the same values.
The next greater value for the pivot is the rightmost value that is still greater than it. After the swap, reversing the suffix turns that non-increasing part into ascending order. That creates the smallest suffix after the smallest possible increase, which is exactly the next permutation.
Algorithm
Move from right to left to find the first position whose value is smaller than the value immediately after it.
If no such position exists, reverse the whole array into ascending order and stop.
Move from the right end to find the first value greater than the chosen position's value.
Swap those two values to make the rightmost possible increase.
Reverse the suffix after the swapped position, then stop because that suffix is now the smallest possible order.
Dry Run
Next Permutation Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Rearranges nums into the next lexicographic permutation. void nextPermutation(vector<int>& nums) { int n = nums.size(); // A single value cannot move to a different permutation. if (n <= 1) { return; } int pivot = n - 2; // Search for the rightmost position that can be increased. while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) { pivot--; } // A fully non-increasing array wraps around to the smallest permutation. if (pivot < 0) { reverse(nums.begin(), nums.end()); return; } int successor = n - 1; // Search from the right for the next larger value. while (nums[successor] <= nums[pivot]) { successor--; } swap(nums[pivot], nums[successor]); // Reverse the non-increasing suffix into the smallest possible order. reverse(nums.begin() + pivot + 1, nums.end()); }};// Driver codeint main() { vector<int> nums = {2, 1, 5, 4, 3, 0, 0}; // instance for class Solution Solution sol; sol.nextPermutation(nums); // Print the array after in-place rearrangement. for (int value : nums) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n), because the pivot search, successor search, and suffix reversal each scan at most the array once.
Space Complexity: O(1), because the rearrangement is done in-place with only a few variables.
Interview follow-up Questions
Changing a position farther to the right keeps the earlier prefix as large as possible without skipping over the immediate next permutation. A change farther left would create a much larger jump.
Be the first to add a comment.