Log inSign up
mediumLeetCodeNot Started

Next Permutation

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1 · Standard Next Permutation:

Input: nums = [1, 2, 3]
Output: [1, 3, 2]
Explanation: The permutation following [1, 2, 3] in lexicographical order is [1, 3, 2].

Example 2 · Maximum Permutation (Wrap Around):

Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Explanation: The array is already the highest permutation, so it resets to the lowest permutation [1, 2, 3].

Example 3 · Pivot in the Middle:

Input: nums = [1, 1, 5]
Output: [1, 5, 1]
Explanation: Next lexicographical order is [1, 5, 1].

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Understanding lexicographical ordering (dictionary order)
  • Right-to-left array traversal
  • In-place subarray reversal using two pointers

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mathematical structure of lexicographical ordering.
  • Identify why any descending suffix represents the maximum possible permutation of its elements.
  • Formulate the 3-step pivot-swap-reverse algorithm in strict O(N) time.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generating the next lexicographical permutation of numbers or characters.
  • Requires in-place modification with O(1) auxiliary space.
  • Suffix monotonicity (descending tail sequence).

Algorithmic Decision Tree:

  • When finding the next permutation: Find the rightmost ascending break nums[i] < nums[i+1], swap with the next greater element to the right, and reverse the suffix after i.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Generate All Permutations in Lexicographical Order

Intuition

Generate all N! permutations recursively, sort them lexicographically, and find the successor.

Algorithm

  1. 1. Use backtracking/recursion to generate all N! permutations.
  2. 2. Sort the generated permutations in lexicographical order.
  3. 3. Search for current configuration and pick the next index (modulo total count).
  4. 4. Total runtime is O(N! * N) and space is O(N!).

Brute Force All Permutations Generation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 4, 2]
Current operationSTEP 1 OF 6
Generate Permutations: Recursively build lexicographical list starting from [1, 2, 3, 4, 5]
Visual state
Values and pointers at this exact step
table
S
1
2
3
4
5
0
↑ Permutation 1
1
2
3
4
PermutationsGenerating...
Count1 of 120
Variables at this step
Permutations
Generating...
Count
1 of 120
Check / comparison
Recursively generate all 5! = 120 permutations in sorted order.
Decision / next transition
Start with lexicographically first: [1, 2, 3, 4, 5].
Why this step matters

Generate Permutations: Recursively build lexicographical list starting from [1, 2, 3, 4, 5].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void nextPermutation(vector<int>& nums) {
17 std::next_permutation(nums.begin(), nums.end());
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> nums = {1, 2, 3};
24 sol.nextPermutation(nums);
25 cout << "Next Permutation: ";
26 for (int x : nums) cout << x << " ";
27 cout << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N! * N) — Generating and sorting N! permutations of length N requires factorial time and space.
  • Space complexity: O(N! * N) — Requires auxiliary space to store all N! permutation arrays.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Find Pivot via Linear Scan & Binary Search Next Greater

Intuition

Scan backwards to find pivot index i where nums[i] < nums[i+1], binary search for smallest element > nums[i] in suffix, swap and reverse.

Algorithm

  1. 1. Find pivot i from right: largest i such that nums[i] < nums[i+1].
  2. 2. If no such i exists, reverse entire array and return.
  3. 3. Use binary search on the descending suffix nums[i+1..n-1] to find smallest element > nums[i].
  4. 4. Swap nums[i] with that element.
  5. 5. Reverse suffix nums[i+1..n-1].

Suffix Search with Sort Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 3, 5, 4, 2]
Current operationSTEP 1 OF 6
Step 1 — Find Pivot: Suffix [5, 4, 2] is decreasing
Visual state
Values and pointers at this exact step
table
S
1
3
5
4
2
0
1
↑ Pivot Idx 1 (val 3)
2
3
4
Pivot Idx1
Pivot Val3
Variables at this step
Pivot Idx
1
Pivot Val
3
Check / comparison
Scan right-to-left: 2 < 4 < 5. First drop at nums[1] (3) < nums[2] (5).
Decision / next transition
Pivot index is 1 (value 3).
Why this step matters

Step 1 — Find Pivot: Suffix [5, 4, 2] is decreasing. The drop occurs at nums[1] = 3.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void nextPermutation(vector<int>& nums) {
17 int n = nums.size();
18 int i = n - 2;
19 while (i >= 0 && nums[i] >= nums[i + 1]) i--;
20
21 if (i >= 0) {
22 int low = i + 1, high = n - 1, best = i + 1;
23 while (low <= high) {
24 int mid = low + (high - low) / 2;
25 if (nums[mid] > nums[i]) {
26 best = mid;
27 low = mid + 1;
28 } else {
29 high = mid - 1;
30 }
31 }
32 swap(nums[i], nums[best]);
33 }
34 reverse(nums.begin() + i + 1, nums.end());
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> nums = {1, 2, 3};
41 sol.nextPermutation(nums);
42 cout << "Next Permutation: ";
43 for (int x : nums) cout << x << " ";
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N) — Linear scan takes O(N), binary search takes O(log N), reversing takes O(N). Total time is O(N).
  • Space complexity: O(1) — All operations are in-place using O(1) extra space.

3. Single-Pass Suffix Drop, Swap & Reverse (Optimal & Standard)

Intuition

Scan from right to find pivot i, find smallest element j > nums[i] from right, swap and reverse suffix.

Algorithm

  1. 1. Initialize i = n - 2. While i >= 0 and nums[i] >= nums[i+1], i--.
  2. 2. If i >= 0: - Let j = n - 1. While nums[j] <= nums[i], j--. - Swap nums[i] with nums[j].
  3. 3. Reverse suffix nums[i+1 .. n-1].
  4. 4. The next lexicographical permutation is formed in-place in O(N) time.

In-Place Pivot Search and Reversal Trace

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [1, 3, 5, 4, 2]
Current operationSTEP 1 OF 8
Step 1 — Scan from Right: 4 > 2
Visual state
Values and pointers at this exact step
table
S
1
3
5
4
2
0
1
2
3
↑ i=3
4
↑ i+1=4
i3
Condition4 > 2
PhaseFind Pivot
Variables at this step
i
3
Condition
4 > 2
Phase
Find Pivot
Check / comparison
nums[3] (4) > nums[4] (2). Decreasing.
Decision / next transition
Continue scanning left for first descent.
Why this step matters

Step 1 — Scan from Right: 4 > 2. Suffix is currently decreasing right-to-left.

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void nextPermutation(vector<int>& nums) {
17 int n = nums.size();
18 int i = n - 2;
19 while (i >= 0 && nums[i] >= nums[i + 1]) i--;
20
21 if (i >= 0) {
22 int j = n - 1;
23 while (nums[j] <= nums[i]) j--;
24 swap(nums[i], nums[j]);
25 }
26 reverse(nums.begin() + i + 1, nums.end());
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> nums = {1, 2, 3};
33 sol.nextPermutation(nums);
34 cout << "Next Permutation: ";
35 for (int x : nums) cout << x << " ";
36 cout << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — All 3 steps run in at most O(N) operations.
  • Space complexity: O(1) — Operates completely in-place. Auxiliary space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Generate All Permutations in Lexicographical OrderO(N! * N)O(N! * N)Generate all N! permutations recursively, sort them lexicographically, and find the successor.Repeated redundant scans over the input.
2.Approach 2: Find Pivot via Linear Scan & Binary Search Next GreaterO(N)O(1)Scan backwards to find pivot index i where nums[i] < nums[i+1], binary search for smallest element > nums[i] in suffix, swap and reverse.Auxiliary memory allocation or sorting step.
3.Approach 3: Single-Pass Suffix Drop, Swap & Reverse (Optimal & Standard)OptimalO(N)O(1)Scan from right to find pivot i, find smallest element j > nums[i] from right, swap and reverse suffix.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Already Highest Permutation [3, 2, 1] — Input: `, Expected: ` —
  • Duplicates Present [1, 5, 1] — Input: `, Expected: ` —
  • Single Element Array [1] — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Next Permutation?

2.Why is the brute force approach suboptimal for large inputs in Next Permutation?

3.Which data structure or technique enables the optimal solution for Next Permutation?

Back to DSA Sheet