ArrayProblem 15 of 36
Next Permutation
Problem Statement
Given an array of integers, rearrange them into the lexicographically next greater permutation. If such arrangement is not possible (array is in descending order), rearrange it as the lowest possible order (ascending).
Example:
- Input:
[1, 2, 3]→ Output:[1, 3, 2] - Input:
[3, 2, 1]→ Output:[1, 2, 3] - Input:
[1, 1, 5]→ Output:[1, 5, 1]
Approach 1: Brute Force
Intuition
Generate all permutations in sorted order, find the current permutation, and return the next one.
Algorithm
- Generate all permutations of the array
- Sort them lexicographically
- Find the current permutation in the sorted list
- Return the next permutation (or first if current is last)
java
import java.util.*;
public class Solution {
private void generatePermutations(int[] nums, int start,
TreeSet<List<Integer>> perms) {
if (start == nums.length) {
List<Integer> perm = new ArrayList<>();
for (int num : nums) perm.add(num);
perms.add(perm);
return;
}
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
generatePermutations(nums, start + 1, perms);
swap(nums, start, i);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void nextPermutationBruteForce(int[] nums) {
TreeSet<List<Integer>> perms = new TreeSet<>((a, b) -> {
for (int i = 0; i < a.size(); i++) {
if (!a.get(i).equals(b.get(i))) {
return a.get(i) - b.get(i);
}
}
return 0;
});
List<Integer> original = new ArrayList<>();
for (int num : nums) original.add(num);
generatePermutations(nums, 0, perms);
List<Integer> next = perms.higher(original);
if (next == null) next = perms.first();
for (int i = 0; i < nums.length; i++) {
nums[i] = next.get(i);
}
}
}Complexity Analysis
- Time Complexity: O(n!) - Generating all permutations
- Space Complexity: O(n!) - Storing all permutations
Approach 2: Single Pass (Optimal)
Intuition
To get the next permutation:
- Find the rightmost element that is smaller than its next element (pivot)
- Find the smallest element to the right of pivot that is larger than pivot
- Swap them
- Reverse the suffix after the pivot position
Algorithm
- Traverse from right, find first decreasing element (pivot at index
i) - If no pivot found, array is in descending order - reverse entire array
- Find smallest element larger than pivot in suffix (at index
j) - Swap elements at
iandj - Reverse the suffix starting at
i + 1
java
public class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
// Step 1: Find the pivot (first decreasing element from right)
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// Step 2: Find smallest element larger than pivot
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap pivot with that element
swap(nums, i, j);
}
// Step 4: Reverse the suffix
reverse(nums, i + 1, n - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}Complexity Analysis
- Time Complexity: O(n) - At most two linear scans
- Space Complexity: O(1) - In-place modification
Visual Example
For array [1, 3, 5, 4, 2]:
Step 1: Find pivot
[1, 3, 5, 4, 2]
^
i=1 (3 < 5, first decreasing from right)
Step 2: Find successor (smallest element > 3 in suffix)
[1, 3, 5, 4, 2]
^
j=3 (4 is smallest element > 3)
Step 3: Swap nums[1] and nums[3]
[1, 4, 5, 3, 2]
Step 4: Reverse suffix after position 1
[1, 4, 2, 3, 5]
Key Takeaways
- Pattern recognition: The suffix in descending order cannot form a larger permutation
- Pivot finding: Look for the first element breaking the descending pattern from right
- Successor selection: Choose the smallest element larger than pivot to minimize increase
- Suffix reversal: Reversing a descending suffix makes it ascending (smallest arrangement)
- This algorithm is used in C++ STL's
next_permutation()function - Edge case: If entire array is descending, reverse to get the smallest permutation