Squares of a Sorted Array

easy two pointers array sorting

Problem

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

Inputnums = [-4, -1, 0, 3, 10]

Output[0, 1, 9, 16, 100]

Squaring gives [16, 1, 0, 9, 100]; sorting yields [0, 1, 9, 16, 100].

nums (sorted, comma-separated)

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    for pos in range(n - 1, -1, -1):
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] * nums[left]
            left += 1
        else:
            result[pos] = nums[right] * nums[right]
            right -= 1
    return result

function sortedSquares(nums) {
  const n = nums.length;
  const result = new Array(n).fill(0);
  let left = 0, right = n - 1;
  for (let pos = n - 1; pos >= 0; pos--) {
    if (Math.abs(nums[left]) > Math.abs(nums[right])) {
      result[pos] = nums[left] * nums[left];
      left++;
    } else {
      result[pos] = nums[right] * nums[right];
      right--;
    }
  }
  return result;
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        for (int pos = n - 1; pos >= 0; pos--) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[pos] = nums[left] * nums[left];
                left++;
            } else {
                result[pos] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

vector<int> sortedSquares(vector<int>& nums) {
    int n = (int)nums.size();
    vector<int> result(n);
    int left = 0, right = n - 1;
    for (int pos = n - 1; pos >= 0; pos--) {
        if (abs(nums[left]) > abs(nums[right])) {
            result[pos] = nums[left] * nums[left];
            left++;
        } else {
            result[pos] = nums[right] * nums[right];
            right--;
        }
    }
    return result;
}

Explanation

The easy way is to square every number and then sort the result, but sorting costs extra time. The clever observation here is that the biggest squares always come from the two ends of a sorted array, because the most negative and the most positive numbers have the largest magnitudes.

So we keep one pointer left at the start and one pointer right at the end. We compare abs(nums[left]) with abs(nums[right]) — whichever has the bigger absolute value gives the bigger square right now.

The trick is that we fill the answer array from the back. The position pos starts at the last index and moves down. Each step we drop the larger square into result[pos] and move that pointer inward (left++ or right--).

Example: nums = [-4, -1, 0, 3, 10]. Compare |-4|=4 and |10|=10; 10 wins, so result[4]=100 and right--. Next compare 4 and |3|=3; 4 wins, so result[3]=16 and left++. Continuing fills [0, 1, 9, 16, 100].

Because each number is placed exactly once and we never sort again, this finishes in a single linear pass.

Time: O(n) Space: O(n)