Interview 150
Squares of a Sorted Array
- Problem
- LC 977
- File
- interview150_LC977SquaresOfASortedArray.java
- Path
- pkg5leetcode/interview150/interview150_LC977SquaresOfASortedArray.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC977SquaresOfASortedArray.java
- Approach
- Fill result from ends comparing absolute values.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Squares of a Sorted Array | LC 9775 * APPROACH: Fill result from ends comparing absolute values.6 * COMPLEXITY: Time O(n), Space O(n)7 */8public class interview150_LC977SquaresOfASortedArray {9 static int[] sortedSquares(int[] nums) {10 int n = nums.length, lo = 0, hi = n - 1;11 int[] res = new int[n];12 for (int i = n - 1; i >= 0; i--) {13 if (Math.abs(nums[lo]) > Math.abs(nums[hi])) {14 res[i] = nums[lo] * nums[lo];15 lo++;16 } else {17 res[i] = nums[hi] * nums[hi];18 hi--;19 }20 }21 return res;22 }23 24 public static void main(String[] args) {25 check(java.util.Arrays.equals(sortedSquares(new int[]{-4, -1, 0, 3, 10}), new int[]{0, 1, 9, 16, 100}), "case1");26 check(java.util.Arrays.equals(sortedSquares(new int[]{-7, -3, 2, 3, 11}), new int[]{4, 9, 9, 49, 121}), "case2");27 System.out.println("all tests passed");28 }29 30 static void check(boolean cond, String name) {31 if (!cond) throw new AssertionError("FAILED: " + name);32 System.out.println(" PASS " + name);33 }34}