refactor 581

fishercoder1534 · fishercoder1534 · commit a6583d022aa6 · 2021-02-25T17:45:44.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_581.java b/src/main/java/com/fishercoder/solutions/_581.java
@@ -34,6 +34,38 @@ public int findUnsortedSubarray(int[] nums) {
     }
 
     public static class Solution2 {
+        /**
+         * Time: O(n)
+         * Space: O(1)
+         * <p>
+         * This is just an alternative way of writing Solution1, credit: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/103057/Java-O(n)-Time-O(1)-Space/106306
+         *
+         * But still, initializing end to be -2 is an art to take care of the corner case as in Solution1.
+         */
+        public int findUnsortedSubarray(int[] nums) {
+            int end = -2;
+            int max = Integer.MIN_VALUE;
+            //go from left to right, find the number that is smaller than the max number on its left side, that should be the end index because it needs to be sorted
+            for (int i = 0; i < nums.length; i++) {
+                max = Math.max(max, nums[i]);
+                if (nums[i] < max) {
+                    end = i;
+                }
+            }
+            int start = -1;
+            int min = Integer.MAX_VALUE;
+            //go from right to left, find the number that is bigger than the min number on its right, that should be the beginning index
+            for (int i = nums.length - 1; i >= 0; i--) {
+                min = Math.min(min, nums[i]);
+                if (nums[i] > min) {
+                    start = i;
+                }
+            }
+            return end - start + 1;
+        }
+    }
+
+    public static class Solution3 {
         /**
          * Time: O(nlogn)
          * Space: O(n)
diff --git a/src/test/java/com/fishercoder/_581Test.java b/src/test/java/com/fishercoder/_581Test.java
@@ -9,12 +9,14 @@
 public class _581Test {
     private static _581.Solution1 solution1;
     private static _581.Solution2 solution2;
+    private static _581.Solution3 solution3;
     private static int[] nums;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _581.Solution1();
         solution2 = new _581.Solution2();
+        solution3 = new _581.Solution3();
     }
 
     @Test
