# Leetcode Next Permutation problem solution

Feb 28, 2023

In the Leetcode Next Permutation problem solution 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

## Solution in C Programming

``````#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#if defined(_MSC_VER)
#define FORCE_INLINE __forceinline
#else
#define FORCE_INLINE __attribute__((always_inline)) inline
#endif

FORCE_INLINE static void swap(int *restrict v1, int *restrict v2)
{
int tmp = *v1;
*v1 = *v2;
*v2 = tmp;
}

static int quicksortCompare(const void *v1, const void *v2)
{
return *(int *)v1 - *(int *)v2;
}

static int splitArray(int *nums, int numsSize)
{
for (int right = numsSize - 1; right >= 1; right--)
if (nums[right] > nums[right - 1])
return right;
return 0;
}

static int searchMinValueIdx(int *restrict nums, int numsSize, int leftIdx, int rightIdx)
{
const int pivot = nums[leftIdx];
int minVal = INT_MAX, minValIdx = -1;
for (; rightIdx < numsSize; rightIdx++)
{
if (nums[rightIdx] > pivot && nums[rightIdx] < minVal)
{
minVal = nums[rightIdx];
minValIdx = rightIdx;
}
}

return minValIdx;
}

static bool __nextPermutation(int *nums, int numsSize)
{
if (numsSize <= 1)
return false;

const int rightArrayIdx = splitArray(nums, numsSize);
if (rightArrayIdx == 0 && numsSize > 0)
{
return __nextPermutation(nums + 1, numsSize - 1);
}
else
{
const int leftArrayIdx = rightArrayIdx - 1;
const int minValIdx = searchMinValueIdx(nums, numsSize, leftArrayIdx, rightArrayIdx);
swap(&nums[leftArrayIdx], &nums[minValIdx]);
qsort(nums + rightArrayIdx, numsSize - rightArrayIdx, sizeof(nums[0]), quicksortCompare);
}

return true;
}

void nextPermutation(int *nums, int numsSize)
{
if (numsSize > 1)
{
if (__nextPermutation(nums, numsSize) == false)
{
qsort(nums, numsSize, sizeof(nums[0]), quicksortCompare);
}
}
}``````

## Solution in C++ Programming

``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
// find the number before the last peak
int i = nums.size() - 2;
while(i >= 0 && nums.at(i) >= nums.at(i + 1)) i--;

// find the number just larger than our number at position i and swap
if(i >= 0){
int j = nums.size() - 1;
while(nums.at(i) >= nums.at(j)) j--;

swap(nums.at(i), nums.at(j));
}

// after swapping, reverse the numbers after our current number at position i
reverse(nums.begin() + i + 1, nums.end());
}
};
``````

## Solution in Java Programming

``````class Solution {
public void swap(int A[],int i,int j){
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
public void nextPermutation(int[] a) {
if(a == null || a.length == 0) return;

int i = a.length-2;
while(i>=0 && a[i] >= a[i+1]) i--;

if(i >=0 ){
int j=a.length-1;
while(a[j] <= a[i]) j--;
swap(a, i, j);
}
reverse(a, i+1, a.length-1);
}

public void reverse(int A[],int i,int j){
while(i<j) swap(A, i++, j--);
}
}``````

## Solution in Python Programming

``````class Solution(object):
def nextPermutation(self, nums):
l=len(nums)-2
r=len(nums)-1
c=0
while l>=0 and len(nums)>1:
if nums[l]>=nums[r]:
l-=1
r-=1
else:
t=min([x for x in nums[l+1:] if x>nums[l]])
ind=[x for x in nums[l+1:]].index(t)+l+1
y=nums[l]
nums[l]=nums[ind]
nums[ind]=y
temp=nums[r:]
temp.sort()
for i in range(len(temp)):
nums[r+i]=temp[i]
l-=1
r-=1
c=+1
break
if c==0:
nums.reverse()``````

## Solution in C# Programming

``````public class Solution {
public void NextPermutation(int[] nums) {
int length = nums.Count();
if(length<=1)
return;

int i;
for (i=length-2; i>=0; i--){
//for(int x=0;x<list.)

//Console.WriteLine(greater);
if(greater!=null)
{
nums[i]=(int)greater;
break;
}

}

var list=new List<int>();

for(int j=0;j<list.Count();j++)
{
nums[j+i+1]=list[j];
}
}

public void InorderTraverse(List<int> list, BT pointer)
{
if(pointer==null)
return;

InorderTraverse(list, pointer.left);
if(pointer.num!=null)
InorderTraverse(list, pointer.right);
}
}

public class BT{
public int? num;
public BT left;
public BT right;

public void Insert(int n){
var pointer=this;
var newnode= new BT();
newnode.num=n;

while(pointer!=null){
if(pointer.num==null || n <= pointer.num)
{
if(pointer.left==null)
{
pointer.left=newnode;
return;
}

pointer=pointer.left;
}
else{
if(pointer.right==null)
{
pointer.right=newnode;
return;
}

pointer=pointer.right;
}
}
}

public int? FindGreaterNum(int n)
{
var pointer=this;
while (pointer!=null)
{
if(pointer.num > n)
{
if(pointer.left == null || pointer.left.num <= n){
var result=pointer.num;
pointer.num=null;
return result;
}
else
pointer=pointer.left;
}
else
pointer=pointer.right;
}

return null;
}

}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.