# Next Permutation

• To find j, we can use a binary search between i and end.
However this may not make it faster in real world, because for a random permutation, i won't be far away from end.
If we know the array is almost sorted, then binary search will be better.

• If given a multitude of random testcases each with very long length, binary search of finding j will be faster.

• In the brute force approach shouldn't the space be O(n!) and not O(n)?
Given n elements produce n! permutations and we need space to store n! permutations.

• For
while (j >= 0 && nums[j] <= nums[i]), there is no need to test j >= 0, as there must be a number is bigger than nums[i].
while (nums[j] <= nums[i]) is enough.

• Your animation makes the illustration perfect! Thumbs up!

• Isn't the time complexity O(n! * n) for the brute force case? We have to compare all of the permutations to the original one/current closest (each comparision requres O(n) time)

• thx for the animation... helps a lot

• Isn't this incorrect? Should be nums[j] >= nums[i] since we are looking for a number that's greater than nums[i] where we found a break in the descending from left to right pattern. Can someone else double check this?

``````            while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
``````

• while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
after this line ,before swap, i think an extra check for j>=0 is required. For Input [1,1] , j may become -1 according to this logic. So only swap when j >= 0 .

• Who can tell me which software can used to draw this type gif

• Great explanation!

• that is wise

• //this is my solution
int lens = nums.length;
int temp = 0;
int start = 0;// 从第几个元素开始升序排列
boolean isPossible = true;
if (lens > 0) {
for (int i = lens - 1; i >= 0; i--) {
if (isPossible) {
for (int j = lens - 1; j > i; j--) {
if (nums[j] > nums[i]) {//find the position to reverse
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
start = i;//Record this position
isPossible = false;
break;
}
}
}

``````		}

}

if (isPossible) {
for (int i = 0; i < (lens+1 )/ 2; i++) {//reverse nums
temp = nums[lens - i - 1];
nums[lens - i - 1] = nums[i];
nums[i] = temp;
}
} else {//reverse nums form start+1 to the end
for (int i = start + 1; i < (lens + start + 1) / 2; i++) {
temp = nums[i];
nums[i] = nums[lens + start - i];
nums[lens + start - i] = temp;
}
}``````

• Cheeky answer using the STL:

``````    void nextPermutation(vector<int>& nums) {
std::next_permutation(nums.begin(), nums.end());
}
``````

:)

• very very good solution！you are so smart!

• wow, so smart!!!!!

• The while loop condition on 'j' can be changed to "j >= i+1" since we do not need to traverse all the way back to j>=0 as we need to find the first larger element to the right of "i-1". Moreover, nums[i] > nums[i-1] due to the previous for loop and when the while loop breaks, the correctness is not affected.

• @shraddheshb. Well, the while loop will end before it reaches ''i'' any way, so it does not make a diffrence in runtime.

• I think the sequential back trace search can be optimized using binary search.

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