Added Next Permutation

vJechsmayr · Oct 1, 2020 · f4ddbe5 · f4ddbe5
1 parent f74b053
commit f4ddbe5
Showing 1 changed file with 16 additions and 0 deletions.
diff --git a/LeetCode/0031_Next_Permutation.py b/LeetCode/0031_Next_Permutation.py
@@ -0,0 +1,16 @@
+class Solution:
+    def nextPermutation(self, nums: List[int]) -> None:
+        i = j = len(nums)-1
+        while i > 0 and nums[i-1] >= nums[i]:
+            i -= 1
+        if i == 0:   # nums are in descending order
+            nums.reverse()
+            return 
+        k = i - 1    # find the last "ascending" position
+        while nums[j] <= nums[k]:
+            j -= 1
+        nums[k], nums[j] = nums[j], nums[k]  
+        l, r = k+1, len(nums)-1  # reverse the second part
+        while l < r:
+            nums[l], nums[r] = nums[r], nums[l]
+            l +=1 ; r -= 1