Problem Statement

Squares of a Sorted Array

You are given an array of whole numbers called nums. It is already sorted in non-decreasing order, which means each number is the same as or bigger than the one before it (negatives can come first). Your job is to square every number, and return a new array of those squares, also sorted from smallest to largest.

easyTwo PointersTwo PointersTime: O(n) · Space: O(n)

Signals to notice

the existing order is part of the cluein-place modificationtwo ends moving inward

Brute force first

Square each element, then sort the result. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Use two pointers at both ends; the larger absolute value goes at the back of the result. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `nums=[-4,-1,0,3,10]`

init: left=0, right=4, pos=4, result=[_,_,_,_,_]
|−4|=4 vs |10|=10 → right wins: result[4]=100, right=3, pos=3
|−4|=4 vs |3|=3 → left wins: result[3]=16, left=1, pos=2
|−1|=1 vs |3|=3 → right wins: result[2]=9, right=2, pos=1
|−1|=1 vs |0|=0 → left wins: result[1]=1, left=2, pos=0
left=right=2: |0|=0 vs |0|=0 → else: result[0]=0, right=1, pos=-1
left>right, stop → return [0,1,9,16,100]

What must stay true

The largest square is always at one of the two ends of the sorted array. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

left = 0; right = n-1; pos = n-1; result = array(n)
while left <= right:
    if abs(nums[left]) > abs(nums[right]):
        result[pos] = nums[left]^2; left += 1
    else:
        result[pos] = nums[right]^2; right -= 1
    pos -= 1
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting that negative numbers squared can be larger than positive ones. The fix is usually to return to the meaning of each move, not just the steps themselves.

Two Pointers Pattern