Accepted python solution with detailed explanation, passed all tests within 90 ms


  • 2
    L

    Please check the comments in the code for the explanation. Let me know if you have any questions.

        class Solution:
            # @param num, a list of integer
            # @return a list of integer
            def nextPermutation(self, num):
                if len(num)<2:
                    return num
                ii,tmp=len(num)-2,[num[-1]]
    # Scan from back of the list to check the location that the first time the digit increase. This index would be recored as ii. At the same time, this non-increasing sublist would be recored in tmp.
                while ii>=0:
                    if num[ii]>=num[ii+1]:   
                        tmp.append(num[ii])
                    else:
                        break
                    ii-=1
    # if ii>=0: that means we got to rearrange the elements from ii to end.
                if ii>=0:
                    jj=len(tmp)  
        # check the smallest digit that is larget than num[ii]. And it would be the new head for this sublist.
                    while jj>=1 and tmp[jj-1]>num[ii]:
                        jj-=1
                    subHead=tmp[jj]
                    tmp[jj]=num[ii]
                    tmp.sort()
                    res=num[0:ii]+[subHead]+tmp
        # if ii==-1, the list is in the reverse order ( the last permutation ). The solution shall be the reverse of the input.
                else:
                    res=tmp
                return res

Log in to reply
 

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