Next Permutation


  • 1

    Click here to see the full article post


  • 0
    C

    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.


  • 0
    A

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


  • 0
    A

    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.


  • 0
    W

    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.


  • 0

    Your animation makes the illustration perfect! Thumbs up!


  • 0
    F

    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)


  • 0
    V

    thx for the animation... helps a lot


  • 0
    V

    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--;
                }
    

  • 0
    A

    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 .


Log in to reply
 

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