31. Next Permutation
Next Permutation (LeetCode 31) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Permutations subpattern.
How to solve Next Permutation
Next Permutation is a Generate Permutations problem, part of Backtracking Patterns. Generate all permutations using backtracking. Handle duplicates and next permutation.
Work towards the solution in these steps:
- Consider how permutations can be ordered lexicographically and how you might move from one permutation to the next in such an order.
- Try to identify a position in the array where you can make a change that will yield a lexicographically larger permutation.
- Think about scanning the array from the end to find the first pair where the previous element is smaller than the next one.
The reference solution runs in O(n) time and O(1) space.
The Next Permutation solution and editorial walks through the full approach with reference code.
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 of arr: [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 <= 100
- 0 <= nums[i] <= 100
Topics and companies
Topics: Array, Two Pointers.
Reported in interviews at Facebook, Amazon, Google, Microsoft, Rubrik, Bloomberg, Apple, Morgan Stanley, Goldman Sachs, Atlassian, tcs.
How to practise Next Permutation on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Next Permutation in the code editor, or read the Next Permutation editorial for a worked solution with its approach and complexity analysis.
Where Next Permutation sits in the DSA pattern sheet
Problems related to Next Permutation
Other problems that use the same Permutations and Backtracking Patterns techniques:
- Permutations — Medium, same subpattern
- Permutation Sequence — Hard, same subpattern
- Permutations II — Medium, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern
Next Permutation FAQ
What is the LeetCode number of Next Permutation?
Next Permutation is LeetCode problem 31, rated Medium.
What pattern is used to solve Next Permutation?
Next Permutation is a Generate Permutations problem. It belongs to the Backtracking Patterns pattern, in the Permutations subpattern.
What is the time complexity of Next Permutation?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Next Permutation?
Next Permutation has been reported in interviews at Facebook, Amazon, Google, Microsoft, Rubrik, Bloomberg, Apple, Morgan Stanley, Goldman Sachs, Atlassian, tcs.