Squares of a Sorted Array

Share

Given an integer array sorted in non-decreasing order, return an array of the squares of each number, sorted in non-decreasing order.

Example 1
Input: [-4,-1,0,3,10] → Output: [0,1,9,16,100]
Example 2
Input: [-7,-3,2,3,11] → Output: [4,9,9,49,121]

Solution Approach

Two pointers from both ends. The largest square is at either end. Fill result array from right to left.

  • lo=0, hi=n-1, pos=n-1.
  • While lo<=hi: compare abs(nums[lo]) with abs(nums[hi]).
  • Place the larger square at result[pos--], advance corresponding pointer.
Java
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int lo = 0, hi = n - 1, pos = n - 1;
        while (lo <= hi) {
            int left = nums[lo] * nums[lo], right = nums[hi] * nums[hi];
            if (left > right) { result[pos--] = left; lo++; }
            else { result[pos--] = right; hi--; }
        }
        return result;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N) for result