A solution to LeetCode Problem 31. Next Permutation in JavaScript
If you’re preparing for technical interviews or want to improve your coding skills, solving practice problems on LeetCode is a great way.
In this post, we’ll discuss a solution to the “31. Next Permutation” problem on LeetCode.
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 ofarr:[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 <= 1000 <= nums[i] <= 100
Solution:
The key to this solution is the use of two pointers, i and j. The pointer i starts at the second-to-last element of the array and moves left until it finds an element that is smaller than the element to its right (or until it reaches the beginning of the array). This element is the pivot element.
Next, the pointer j starts at the end of the array and moves left until it finds an element that is larger than the pivot element. This element is the successor element.
Once the pivot and successor elements have been found, the code swaps their values and then reverses the elements to the right of the pivot element. This results in the next permutation of the given array.
Here is the implementation of this solution in JavaScript:
var nextPermutation = function(nums) {
let j = nums.length – 1, i = j – 1;
while (nums[i + 1] <= nums[i]) i–;
if (~i) {
while (nums[j] <= nums[i]) j–;
swap(nums, i, j);
}
for (let k = i + 1, stop = (i + nums.length) / 2; k < stop; k++) {
swap(nums, k, nums.length – k + i);
}
};
function swap(nums, i, j) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
Explanation:
The code first initializes two variables: i and j. i is set to the second to last element of the array, and j is set to the last element.
Then, the code enters a loop that continues as long as nums[i + 1] <= nums[i]. Inside the loop, i is decremented by 1. This loop is finding the first i such that nums[i] < nums[i + 1].
After the loop, the code checks if i is not equal to -1 (indicated by the ~ operator). If i is not equal to -1, the code enters another loop that continues as long as nums[j] <= nums[i]. Inside the loop, j is decremented by 1. This loop is finding the first j such that nums[j] > nums[i].
After the loop, the code swaps the values at indices i and j using the swap function.
Finally, the code enters a loop that iterates from i + 1 to halfway between i + 1 and the end of the array. Inside the loop, the code swaps the value at index k with the value at index nums.length – k + i. This rearranges the elements of the array from index i + 1 to the end of the array into their lexicographically smallest permutation.
The time complexity of this code is O(n), where n is the length of the array nums. This is because the code makes at most two passes through the array, each taking O(n) time, for a total of O(n) time.
I hope this helps as a reference for solving LeetCode Problem Next Permutation in JavaScript! Let me know if you have any questions or if you’d like to see any additional examples.