A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
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).
arr = [1,2,3] is [1,3,2].arr = [2,3,1] is [3,1,2].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] <= 100Problem Overview: Given an integer array, rearrange the numbers into the next lexicographically greater permutation. If such a permutation does not exist (the array is in descending order), rearrange it to the lowest possible order. The key constraint: perform the transformation in-place with constant extra space.
Approach 1: Brute Force - Generate All Permutations (O(n! * n) time, O(n!) space)
The most straightforward idea is to generate every permutation of the array, sort them lexicographically, then find the permutation immediately after the current one. You can build permutations using backtracking or recursion. After generating them, locate the current configuration and return the next entry in the sorted list.
This approach is conceptually simple but extremely inefficient. Generating permutations costs O(n!), and each permutation comparison costs O(n). Memory usage also explodes because every permutation must be stored. This method is only useful for understanding the problem definition or verifying small test cases.
Approach 2: Lexicographical Order Approach (O(n) time, O(1) space)
The optimal solution relies on how permutations are ordered lexicographically. Scan the array from right to left to find the first index i where nums[i] < nums[i+1]. This position marks the pivot where the increasing sequence from the right breaks. Everything to the right of this pivot forms a descending suffix.
Next, scan again from the right to find the smallest element greater than nums[i]. Swap these two values. This ensures the new prefix becomes the next larger candidate. Finally, reverse the suffix starting from i+1 to the end of the array. Since the suffix was originally in descending order, reversing it produces the smallest possible ordering.
The algorithm touches each element at most a few times: one backward scan, one swap search, and one suffix reversal. That keeps the time complexity at O(n) and space complexity at O(1). The suffix reversal can be implemented efficiently using the two pointers technique.
This problem primarily involves careful index manipulation on an array. The key insight is recognizing that permutations follow predictable lexicographical transitions, so you never need to generate all possibilities.
Recommended for interviews: The lexicographical order approach is the expected solution. Interviewers want to see that you recognize the pivot point, perform the correct swap, and reverse the suffix in-place. Mentioning the brute force permutation idea demonstrates understanding of the problem space, but implementing the O(n) solution shows strong algorithmic thinking and familiarity with permutation ordering.
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.
C++
Java
Python
C#
JavaScript
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 | Time | Space | When to Use |
|---|---|---|---|
| Generate All Permutations (Brute Force) | O(n! * n) | O(n!) | Only for understanding the problem or verifying small inputs |
| Lexicographical Order Approach | O(n) | O(1) | General case and expected interview solution |
| STL / Built-in next_permutation | O(n) | O(1) | When using C++ STL or library utilities that implement the same logic |
Next Permutation - Intuition in Detail 🔥 | Brute to Optimal • take U forward • 611,629 views views
Watch 9 more video solutions →Practice Next Permutation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor