Edit Problem

Title

Problem URL

Difficulty

Tags

Two Pointers

Go file path (optional)

Notes (optional)

## What It Does

This function returns a new array of squared values in **ascending order**, given a sorted array that may contain negative numbers.

The key insight is that in a sorted array with negatives, the largest squares are always at the two ends (e.g. `[-4, -1, 0, 2, 3]` — the largest squares come from `-4` and `3`, not the middle). So it uses two pointers from the outside in, filling the result array from **right to left** with the larger square at each step.

For example, `[-4, -1, 0, 2, 3]` → `[0, 1, 4, 4, 9]`.

---

## Complexity Analysis

**Time Complexity: O(n)**

`start` and `end` move toward each other one step at a time, and each iteration fills exactly one position in `squares`. The loop runs exactly `n` times total — a single linear pass.

**Space Complexity: O(n)**

The `squares` slice allocated with `make([]int, n)` scales linearly with input size. If you count only *auxiliary* space (excluding the required output), it's O(1) — but since the output array is explicitly allocated here, O(n) is the honest answer.

---

## A Few Notes

**Why not just square-and-sort?** That would be O(n log n). This approach is O(n) by exploiting the already-sorted structure — a meaningful improvement for large inputs.

**The right-to-left fill is the clever part.** Filling left-to-right would require knowing the *smallest* square at each step, which is harder to determine since you'd need to handle the convergence of negatives and positives. Filling from the largest down is unambiguous.

First solved

Mar 3, 2026