Squares of a Sorted Array Without Sorting Again

This one is a Easy-rated classic reported from Meta, Uber, Amazon interviews: "Squares of a Sorted Array". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Two Pointers pattern on sight. Part 4 of 12 in the Two Pointers arc.

The Problem

Given an integer array nums sorted in non-decreasing order — possibly containing negatives — return an array of the squares of each number, also sorted. The obvious square-then-sort costs O(n log n); the interviewer wants O(n).

Input:  nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Squaring gives [16, 1, 0, 9, 100], which is no longer sorted.

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

Squaring destroys sortedness only because negatives flip: absolute values decrease, then increase — a valley shape. The largest square must sit at one of the two ends, and largest lives at the edges is a converging-pointers invitation.

The Approach

Compare absolute values at both ends. The bigger one produces the largest remaining square, so write it into the result from the back and move that pointer inward. Repeat until the pointers cross; the output fills right to left in perfect order.

Filling backwards is the detail people fumble — filling smallest-first from the front requires knowing where the valley bottom is, which is an unnecessary extra scan.

Python Solution

def sorted_squares(nums: list[int]) -> list[int]:
    """Squares of a sorted (possibly negative) array, in sorted order."""
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    for slot in range(n - 1, -1, -1):
        if abs(nums[left]) > abs(nums[right]):
            result[slot] = nums[left] * nums[left]
            left += 1
        else:
            result[slot] = nums[right] * nums[right]
            right -= 1
    return result

Complexity

• Time: O(n) — one element is placed per iteration
• Space: O(n) — the output array; auxiliary space is O(1)

Interview Tips and Follow-Ups

• Say the O(n log n) baseline first, then beat it — showing the ladder is worth as much as the final answer.
• All-negative and all-positive inputs are the edge cases that expose off-by-ones in the backward fill.
• Distinguish output space from auxiliary space when the interviewer asks for complexity — conflating them is a common ding.

That wraps part 4 of the Two Pointers arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.