# Accepted Java Solution O(n) with explanations

• Algorithm:

• 1.Traverse from right and identify the element such that num[i] < num[i+1] i.e. it breaks descending rule
• a) If match not found we have reached the last element, so reverse the order of all elements
• b) If match found, then traverse from right and identify the first element say num[i+x] that is greater than num[i]. Swap num[i] and num[i+x] and then reverse the order of elements to the right of num[i+x]

Examples:
(i) 3,2,1 -> 1,2,3 (1a)
(ii) 1,3,2 -> 2,1,3 (1b)
Steps:

• 1 breaks descending rule
• Swap(1,2) i.e. 2,3,1
• Reverse all elements to the the right of 2 i.e. 2,1,3
``````public static int[] nextPermutation(int[] nums) {
if(nums.length == 0) {
return null;
}

boolean isMatch = false;
int i = nums.length-2;
for( ; i>=0; ) {
if(nums[i] < nums[i+1]) {
isMatch = true;
break;
}
i--;
}

if(isMatch) {
//Found an element that breaks the descending rule (1b)
//Find an element > nums[i+x] that is greater than num[i]
int j=nums.length - 1;
for(; j>i;) {
if(nums[j] > nums[i])
break;
j--;
}
swap(nums, i, j);
//Note: Since i and j are swapped, reverse the elements to right of index i+1
reverse(nums, i+1, nums.length-1);
} else {
//Not Found an element that breaks the descending rule (1a), i.e. we have reached the end of lexicographical order
//Reverse all elements to get the first element in lexicographical order
reverse(nums, 0, nums.length-1);
}

return nums;
}

public static void reverse(int[] nums, int s, int e){
while(s < e){
swap(nums, s, e);
s++;
e--;
}
}

public static void swap(int[] nums, int s, int e){
int t = nums[s];
nums[s] = nums[e];
nums[e] = t;
}

public static void main(String[] args) {
//Tests
nextPermutation(new int[] {1,3,2}); //2,1,3
nextPermutation(new int[] {3,2,1}); //1,2,3
}
``````

Note: I have a return type of int[] to allow running some unit tests. Hope this helps.
Special thanks to hot13399 who provided the detailed algorithm here: https://leetcode.com/problems/next-permutation/discuss/13866

• This post is deleted!

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