Squares of a Sorted Array

You are given an integer list nums that is already sorted in non-decreasing order. It may contain negative numbers, zero and positive numbers.

Return a new list containing the square of every element, also sorted in non-decreasing order.

Squaring and then sorting is easy; try to produce the result in a single linear pass instead.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

Pattern Path · Two Pointers · problem 18 of 169

Start simple

Square every element and sort the result: O(n log n) time.

The key idea

Squaring maps each value to its absolute value squared, so order is decided by distance from zero. In a sorted list, the values farthest from zero sit at the two ends: the left end holds the most negative values and the right end the most positive. The values closest to zero are somewhere in the middle.

That means the largest remaining square is always at one of the two ends. Place a pointer lo at the start and hi at the end, and fill the result from its last slot backward. At each step compare |nums[lo]| with |nums[hi]|, write the larger one's square into the current slot, and move that pointer inward.

Each element is placed exactly once, so the whole result is built in one pass. Filling from the back is the key trick: trying to fill from the front would require finding the value closest to zero first, which is harder.

Complexity

• Time: O(n)
• Space: O(n) for the output (O(1) extra)

Python

class Solution:
    def sortedSquares(self, nums):
        n = len(nums)
        result = [0] * n
        lo, hi = 0, n - 1
        # The largest remaining square is always at one of the two ends.
        for write in range(n - 1, -1, -1):
            if abs(nums[lo]) > abs(nums[hi]):
                result[write] = nums[lo] * nums[lo]
                lo += 1
            else:
                result[write] = nums[hi] * nums[hi]
                hi -= 1
        return result

JavaScript

var sortedSquares = function(nums) {
  const n = nums.length;
  const result = new Array(n);
  let lo = 0, hi = n - 1;
  // The largest remaining square is always at one of the two ends.
  for (let write = n - 1; write >= 0; write--) {
    if (Math.abs(nums[lo]) > Math.abs(nums[hi])) {
      result[write] = nums[lo] * nums[lo];
      lo++;
    } else {
      result[write] = nums[hi] * nums[hi];
      hi--;
    }
  }
  return result;
};

What the interviewer is checking

It tests whether you notice the existing sorted structure and use converging two pointers to merge it, instead of discarding that structure with a fresh sort.

Mistakes to avoid

• Filling the result from the front with the smaller square, which needs the zero crossing and is easy to get wrong.
• Comparing raw values instead of absolute values (or squares) at the two ends.
• Forgetting the all-negative and all-positive cases, where one pointer never moves.

Follow-ups to expect

• Can you do it in place without an output array? (Not in linear time easily; discuss.)
• What if you applied f(x) = ax² + bx + c instead? (Same two-pointer merge, direction depends on a.)
• How would you merge two sorted lists generally? (Same pointer-per-list comparison.)

In real software

Merging two sorted streams, as in merge sort or database merge joins, uses the same pointer-per-sorted-run comparison.

Practice next