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] <= 100The goal of Next Permutation is to rearrange an array of numbers into the next lexicographically greater permutation. If such an arrangement is not possible, the array should be transformed into the smallest possible order. A brute-force method would generate all permutations and then locate the next one, but this approach is highly inefficient.
The optimal idea relies on analyzing the array from right to left. First, identify a pivot point where the order stops increasing. This indicates the position where a slightly larger value can produce the next permutation. Then locate the smallest element on the right side that is greater than the pivot and swap them. Finally, rearrange the suffix to form the smallest possible sequence, typically by reversing it.
This strategy works because the suffix is already in decreasing order. By making a minimal change at the pivot and reordering the remaining elements, we achieve the next lexicographical arrangement efficiently in O(n) time with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Pivot + Swap + Reverse (Optimal) | O(n) | O(1) |
take U forward
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.
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.
1#include <stdio.h>
2
3void swap(int *a, int *b) {
4 int temp = *a;
5
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Next Permutation is a well-known interview problem and variations of it appear in FAANG and other top tech company interviews. It tests understanding of arrays, in-place manipulation, and lexicographical ordering concepts.
After swapping the pivot with the next greater element, the suffix remains in decreasing order. Reversing it converts that section into the smallest possible order, ensuring the resulting permutation is the immediate next lexicographical one.
The optimal approach scans the array from right to left to find a pivot where the order decreases. It then swaps the pivot with the next greater element on its right and reverses the suffix to produce the next lexicographical permutation. This method runs in O(n) time and uses constant space.
The problem primarily works with arrays since permutations are generated by rearranging elements in-place. No additional complex data structures are required, making it efficient in both time and space.