# Accepted Recursive Java Solution

• The idea is to reduce the problem into a swap operation of two rightmost elements (base case). If that is not possible we expand by adding the next immediate element and try to swap it with the smallest available number. When that swap is successful we need to sort the rest of the unswapped elements to the right to account for lexicography. If that swap is not successful that means we don't have a solution and return the array in ascending order.

``````public static void nextPermutation(int[] nums)
{
if(nums.length == 1)
return;
boolean solved = solveSmaller(nums, 0, nums.length - 1);
if(!solved){
Arrays.sort(nums);
}
}

static boolean solveSmaller(int nums[], int begin, int end){
if(end - begin + 1 == 2){ //base case, compare two elements and swap if possible
if(nums[begin] < nums[end]){
swap(nums, begin, end);
return true;
}else{
return false; //no swap available
}
}else{
boolean isSmallerSolvable = solveSmaller(nums, begin + 1, end);
if(isSmallerSolvable){
return true;
}else{ //compare the initial number with the rest and pick the smallest bigger number than the initial, and swap them
int smallestBiggerIndex = pickSmallestBigger(nums[begin], nums, begin + 1); //O(n) operation
if(smallestBiggerIndex == -1) {
return false;
}else{
swap(nums, begin, smallestBiggerIndex);
Arrays.sort(nums, begin + 1, nums.length); //now that most significant index is at its place, the rest of the array should be in ascending order to satisfy lexicography
return true;
}
}
}
}

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

static int pickSmallestBigger(int num, int nums[], int begin){
int pickedIndex = -1;
int smallestBigger = Integer.MAX_VALUE;
for(int i = begin; i < nums.length; i++)
{
if(nums[i] > num){
if(nums[i] < smallestBigger){
smallestBigger = nums[i];
pickedIndex = i;
}
}
}
return pickedIndex;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.