Next Permutation Leetcode Solution

In this post, we are going to solve theÂ Next Permutation Leetcode SolutionÂ problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Problem

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.

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 <= 100`
• `0 <= nums[i] <= 100`

Now, letâ€™s see the leetcode solution ofÂ Next Permutation Leetcode Solution.

Next Permutation Leetcode Solution in Python

```class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)

# From back to front, find the first num < nums[i + 1]
i = n - 2
while i >= 0:
if nums[i] < nums[i + 1]:
break
i -= 1

# From back to front, find the first num > nums[i], swap it with nums[i]
if i >= 0:
for j in range(n - 1, i, -1):
if nums[j] > nums[i]:
nums[i], nums[j] = nums[j], nums[i]
break

def reverse(nums: List[int], l: int, r: int) -> None:
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1

# Reverse nums[i + 1..n - 1]
reverse(nums, i + 1, len(nums) - 1)
```

Next PermutationLeetcode Solutionin CPP

```class Solution {
public:
void nextPermutation(vector<int>& nums) {
const int n = nums.size();

// From back to front, find the first num < nums[i + 1]
int i;
for (i = n - 2; i >= 0; --i)
if (nums[i] < nums[i + 1])
break;

// From back to front, find the first num > nums[i], swap it with nums[i]
if (i >= 0)
for (int j = n - 1; j > i; --j)
if (nums[j] > nums[i]) {
swap(nums[i], nums[j]);
break;
}

// Reverse nums[i + 1..n - 1]
reverse(nums, i + 1, n - 1);
}

private:
void reverse(vector<int>& nums, int l, int r) {
while (l < r)
swap(nums[l++], nums[r--]);
}
};
```

Next Permutation Leetcode Solution in Java

```class Solution {
public void nextPermutation(int[] nums) {
final int n = nums.length;

// From back to front, find the first num < nums[i + 1]
int i;
for (i = n - 2; i >= 0; --i)
if (nums[i] < nums[i + 1])
break;

// From back to front, find the first num > nums[i], swap it with nums[i]
if (i >= 0)
for (int j = n - 1; j > i; --j)
if (nums[j] > nums[i]) {
swap(nums, i, j);
break;
}

// Reverse nums[i + 1..n - 1]
reverse(nums, i + 1, n - 1);
}

private void reverse(int[] nums, int l, int r) {
while (l < r)
swap(nums, l++, r--);
}

private void swap(int[] nums, int i, int j) {
final int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```

Note:Â This problemÂ Next Permutation is generated byÂ LeetcodeÂ but the solution is provided byÂ Chase2learn This tutorial is only forÂ EducationalÂ andÂ LearningÂ purposes.

Sharing Is Caring