Update Next Permutation.java

varunu28 · web-flow · commit 60cdab24eb68 · 2022-04-21T21:22:14.000+05:30
diff --git a/Medium/Next Permutation.java b/Medium/Next Permutation.java
@@ -1,32 +1,29 @@
 class Solution {
   public void nextPermutation(int[] nums) {
-    boolean flag = true;
-    int right = nums.length - 1;
-    int start = right;
-    while (start >= 1) {
-      if (nums[start] > nums[start - 1]) {
-        int idx = right;
-        while (nums[idx] <= nums[start - 1]) {
-          idx--;
-        }
-        int temp = nums[start - 1];
-        nums[start - 1] = nums[idx];
-        nums[idx] = temp;
-        flag = false;
-        break;
-      }
-      start--;
-    }
-    if (flag) {
-      Arrays.sort(nums);
+    if (nums.length <= 1) {
       return;
     }
-    while (start < right) {
-      int temp = nums[start];
-      nums[start] = nums[right];
-      nums[right] = temp;
-      start++;
-      right--;
+    int idx = nums.length - 2;
+    while (idx >= 0 && nums[idx] >= nums[idx + 1]) {
+      idx--;
+    }
+    if (idx >= 0) {
+      int endIdx = nums.length - 1;
+      while (nums[endIdx] <= nums[idx]) {
+        endIdx--;
+      }
+      swap(nums, idx, endIdx);
+    }
+    int startIdx = idx + 1;
+    int endIdx = nums.length - 1;
+    while (startIdx < endIdx) {
+      swap(nums, startIdx++, endIdx--);
     }
   }
+  
+  private void swap(int[] nums, int idxOne, int idxTwo) {
+    int temp = nums[idxOne];
+    nums[idxOne] = nums[idxTwo];
+    nums[idxTwo] = temp;
+  }
 }
