Last updated on January 20th, 2025 at 04:14 am
Here, we see the Next Permutation LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Two-Pointers
Companies
Level of Question
Medium
Next Permutation LeetCode Solution
Table of Contents
1. Problem Statement
Given an array of integers nums, find the next permutation of nums.
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.
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]
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Two Pointers”. The algorithm involves using two pointers to traverse and manipulate the array in-place. Specifically:
- One pointer (
kori) is used to find the first decreasing element from the right. - Another pointer (
lorj) is used to find the smallest element larger than the first pointer’s value. - The two pointers are then used to reverse the subarray to achieve the next lexicographical permutation.
This pattern is commonly used when working with arrays or strings to solve problems involving rearrangement or searching for specific conditions.
3. Code Implementation in Different Languages
3.1 Next Permutation C++
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size(), k, l;
for (k = n - 2; k >= 0; k--) {
if (nums[k] < nums[k + 1]) {
break;
}
}
if (k < 0) {
reverse(nums.begin(), nums.end());
} else {
for (l = n - 1; l > k; l--) {
if (nums[l] > nums[k]) {
break;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
}
}
};
3.2 Next Permutation Java
class Solution {
public void nextPermutation(int[] nums) {
int dest = nums.length - 2;
for (; 0 <= dest && nums[dest] >= nums[dest + 1]; --dest)
;
if (0 <= dest) {
int target = nums.length - 1;
for (; nums[dest] >= nums[target]; --target)
;
int tmp = nums[dest];
nums[dest] = nums[target];
nums[target] = tmp;
}
for (int end = nums.length - 1; dest + 1 < end; ) {
int tmp = nums[++dest];
nums[dest] = nums[end];
nums[end--] = tmp;
}
}
}
3.3 Next Permutation JavaScript
var nextPermutation = function(nums) {
const swap = (a, b) => [nums[a],nums[b]] = [nums[b],nums[a]]
let len = nums.length - 1, i, j
for (i = len - 1; nums[i] >= nums[i+1];) i--
for (let k = i+1; len > k; k++, len--) swap(k,len)
if (~i) {
for (j = i + 1; nums[i] >= nums[j];) j++
swap(i,j)
}
};
3.4 Next Permutation Python
class Solution(object):
def nextPermutation(self, nums):
i = j = len(nums)-1
while i > 0 and nums[i-1] >= nums[i]:
i -= 1
if i == 0: # nums are in descending order
nums.reverse()
return
k = i - 1 # find the last "ascending" position
while nums[j] <= nums[k]:
j -= 1
nums[k], nums[j] = nums[j], nums[k]
l, r = k+1, len(nums)-1 # reverse the second part
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l +=1 ; r -= 1
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(1) |
| Python | O(n) | O(1) |