Next Permutation - Solution & Explanation
Problem Statement
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
- For example, for
arr = [1,2,3], the following are all the permutations ofarr:[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
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).
- For example, the next permutation of
arr = [1,2,3]is[1,3,2]. - Similarly, the next permutation of
arr = [2,3,1]is[3,1,2]. - While the next permutation of
arr = [3,2,1]is[1,2,3]because[3,2,1]does not have a lexicographical larger rearrangement.
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:
Input: nums = [1,2,3] Output: [1,3,2]
Example 2:
Input: nums = [3,2,1] Output: [1,2,3]
Example 3:
Input: nums = [1,1,5] Output: [1,5,1]
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100
Approach Overview
Problem Overview: Given an integer array, rearrange the numbers into the next lexicographically greater permutation. If such ordering is not possible (the array is in descending order), transform it into the smallest permutation by sorting it in ascending order.
Approach 1: Brute Force - Generate All Permutations (O(n! * n) time, O(n!) space)
Generate every permutation of the array, store them, then sort the permutations lexicographically. Locate the current permutation and return the next one in the sorted list. If the current permutation is the last, return the first permutation (sorted ascending). This approach relies on exhaustive generation and comparison, which quickly becomes infeasible as n grows because factorial growth dominates runtime and memory usage.
Approach 2: Lexicographical Order Approach (O(n) time, O(1) space)
This method constructs the next permutation directly using a deterministic pattern. Start from the right and find the first index i where nums[i] < nums[i+1]. This position marks the pivot where the ascending order breaks. Then scan from the end again to find the smallest element greater than nums[i] and swap them. Finally, reverse the suffix starting from i+1 to the end to obtain the smallest possible ordering after the pivot.
The key insight: the suffix after the pivot is always in descending order. Reversing it converts it to the smallest lexicographic arrangement. The algorithm performs a few linear scans and a reversal, making the overall complexity O(n). The operation modifies the array in-place without extra memory. This pattern often appears in array manipulation problems and can be implemented using simple index traversal or two pointers during the reversal step.
Approach 3: Built-in next_permutation (O(n) time, O(1) space)
Languages like C++ provide next_permutation in the STL, which internally implements the same lexicographical algorithm. It finds the pivot, swaps with the next larger element, and reverses the suffix. This approach is convenient when library utilities are allowed, but interviews usually expect you to implement the algorithm manually to demonstrate understanding of permutation ordering logic.
Recommended for interviews: The lexicographical order approach. Interviewers expect the O(n) in-place algorithm because it demonstrates understanding of permutation ordering and careful array manipulation. Explaining the brute force idea shows awareness of the search space, but implementing the pivot-swap-reverse sequence proves you can optimize it efficiently.
Approach 1: Lexicographical Order Approach
This approach involves transforming the current permutation into its next lexicographical order. The key operations include identifying the longest non-increasing suffix and swapping elements to get a slightly larger permutation, followed by reversing the suffix to get the lowest order.
The provided C solution modifies the array in-place to compute the next permutation. It starts by searching for the first pair where a number is less than the immediate right neighbor, moving left from the end of the array. Upon finding this value, a subsequent search for the smallest number larger than it is performed within the right section of the array. Finally, this section is reversed to form the smallest lexicographical order possible.
Complexity
Time Complexity: O(n), where n is the number of elements in the array. This is due to the maximal traversal and operations over the array.
Space Complexity: O(1) since the operation is performed in-place with constant memory usage.
Approach 2: Two traversals
We first traverse the array from back to front and find the first position i where nums[i] \lt nums[i + 1].
Then traverse the array from back to front again and find the first position j where nums[j] \gt nums[i]. Swap nums[i] and nums[j], and then reverse the elements from nums[i + 1] to nums[n - 1], the next permutation can be obtained.
The time complexity is O(n) and the space complexity is O(1). Where n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Lexicographical Order Approach | Time Complexity: O(n), where n is the number of elements in the array. This is due to the maximal traversal and operations over the array. |
| Two traversals | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Permutations (Brute Force) | O(n! * n) | O(n!) | Conceptual understanding or very small arrays |
| Lexicographical Order Algorithm | O(n) | O(1) | General case and expected interview solution |
| STL / Built-in next_permutation | O(n) | O(1) | When library utilities are allowed in production code |
Video Solution
Next Permutation - Intuition in Detail 🔥 | Brute to Optimal • take U forward • 1,075,709 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Next Permutation easy or hard?
How to solve Next Permutation in O(n)?
What is the best approach for Next Permutation?
What data structure is used in Next Permutation?
What is the time complexity of Next Permutation?
Next Permutation Python or Java solution approach?
Is Next Permutation asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Next Permutation with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor