add a solution for 977

fishercoder1534 · fishercoder1534 · commit 1efa219933cb · 2021-09-13T09:17:48.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_977.java b/src/main/java/com/fishercoder/solutions/_977.java
@@ -4,13 +4,35 @@
 
 public class _977 {
     public static class Solution1 {
-        public int[] sortedSquares(int[] A) {
-            int[] result = new int[A.length];
-            for (int i = 0; i < A.length; i++) {
-                result[i] = (int) Math.pow(A[i], 2);
+        /**
+         * O(nlogn) solution
+         */
+        public int[] sortedSquares(int[] nums) {
+            int[] result = new int[nums.length];
+            for (int i = 0; i < nums.length; i++) {
+                result[i] = (int) Math.pow(nums[i], 2);
             }
             Arrays.sort(result);
             return result;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * O(n) solution
+         */
+        public int[] sortedSquares(int[] nums) {
+            int[] ans = new int[nums.length];
+            for (int i = nums.length - 1, left = 0, right = nums.length - 1; i < nums.length && left <= right; i--) {
+                if (Math.abs(nums[left]) < Math.abs(nums[right])) {
+                    ans[i] = nums[right] * nums[right];
+                    right--;
+                } else {
+                    ans[i] = nums[left] * nums[left];
+                    left++;
+                }
+            }
+            return ans;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_977Test.java b/src/test/java/com/fishercoder/_977Test.java
@@ -7,23 +7,27 @@
 import static org.junit.Assert.assertArrayEquals;
 
 public class _977Test {
-  private static _977.Solution1 solution1;
-  private static int[] A;
+    private static _977.Solution1 solution1;
+    private static _977.Solution2 solution2;
+    private static int[] A;
 
-  @BeforeClass
-  public static void setup() {
-    solution1 = new _977.Solution1();
-  }
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _977.Solution1();
+        solution2 = new _977.Solution2();
+    }
 
-  @Test
-  public void test1() {
-    A = new int[] {-4, -1, 0, 3, 10};
-    assertArrayEquals(new int[] {0, 1, 9, 16, 100}, solution1.sortedSquares(A));
-  }
+    @Test
+    public void test1() {
+        A = new int[]{-4, -1, 0, 3, 10};
+        assertArrayEquals(new int[]{0, 1, 9, 16, 100}, solution1.sortedSquares(A));
+        assertArrayEquals(new int[]{0, 1, 9, 16, 100}, solution2.sortedSquares(A));
+    }
 
-  @Test
-  public void test2() {
-    A = new int[] {-7, -3, 2, 3, 11};
-    assertArrayEquals(new int[] {4, 9, 9, 49, 121}, solution1.sortedSquares(A));
-  }
+    @Test
+    public void test2() {
+        A = new int[]{-7, -3, 2, 3, 11};
+        assertArrayEquals(new int[]{4, 9, 9, 49, 121}, solution1.sortedSquares(A));
+        assertArrayEquals(new int[]{4, 9, 9, 49, 121}, solution2.sortedSquares(A));
+    }
 }
