Advertisement
Iam_Sandeep

Find next Greater number Next Permutation(Inplace)

Jul 6th, 2022 (edited)
847
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.42 KB | None | 0 0
  1. class Solution:
  2.     def nextGreaterElement(self, num: int) -> int:
  3.         arr=list(str(num))
  4.         n=len(arr)
  5.         i=n-2#3462431
  6.         #Find peak point at which decreasing order breaks from right to left
  7.         while i>=0 and arr[i]>=arr[i+1]:
  8.             i-=1
  9.         #If there is no peak return -1 [3462][431]
  10.         if i==-1:
  11.             return -1
  12.         else:
  13.            #Now find next immediate greater number while traversing from n-1 to peak point.
  14.            #If you found swap and break[3463][421]
  15.            #Now Reverse the array from peak point to last elementv[3463][124]------>ans
  16.             for j in range(n-1,i,-1):
  17.                 if arr[i]<arr[j]:
  18.                     arr[i],arr[j]=arr[j],arr[i]
  19.                     break
  20.             arr[i+1:]=arr[i+1:][::-1]
  21.             t=int(''.join(arr))
  22.             return t if t<(1<<31) else  -1
  23. class Solution:
  24.     def nextPermutation(self, a: List[int]) -> None:
  25.         def swap(x,y,a):
  26.             a[x],a[y]=a[y],a[x]
  27.         n=len(a)
  28.         i=n-1
  29.         while i>=1:
  30.             if a[i]>a[i-1]:
  31.                 for j in range(i,n):
  32.                     if a[j]>a[i-1]:
  33.                         next_swap=j
  34.                     else:
  35.                         break
  36.                 swap(next_swap,i-1,a)
  37.                 a[i:]=sorted(a[i:])
  38.                 break
  39.             else:i=i-1
  40.         if i==0:
  41.             a.reverse()
  42.        
  43.            
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement