← DSA Atlas
Dedicated problem page · #977

Squares of a Sorted Array

EasyTwo PointersMerge outward from the largest magnitudeTwo pointers
Solve on LeetCode ↗
977
EasyTwo PointersTwo pointersMerge outward from the largest magnitude

Squares of a Sorted Array

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

Open official problem prompt ↗
In plain English

Produce the sorted list of squares of an already-sorted array in linear time.

Picture it like this

Two lines of people ordered by height meeting at the door; you repeatedly admit whoever is taller of the two front-most, filling a hall from the back forward so the tallest stands at the far end.

Example
Input
nums = [-4, -1, 0, 3, 10]
Output
[0, 1, 9, 16, 100]
Why
Squaring gives [16, 1, 0, 9, 100]; sorted non-decreasing that is [0, 1, 9, 16, 100].
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums is sorted in non-decreasing order
Pattern lesson

See the pattern, then code

Merge outward from the largest magnitude
Recognition clue

Squaring a sorted array makes the largest squares appear at the two ends (most-negative and most-positive), so a two-pointer merge from the ends produces sorted output without re-sorting.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. In a sorted array the biggest absolute values sit at the extremes. Compare the two ends, take whichever has the larger magnitude, square it, and place it at the current back of the result — filling the answer from largest down to smallest.

New words, made simpleKnow these before the algorithm
Magnitude
Absolute value of a number, which determines the size of its square.
Fill from the back
Writing results starting at the last index and moving toward index 0.
Non-decreasing order
Each element is greater than or equal to the previous one; ties allowed.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Square then sort

Simple but ignores the existing order, paying an unnecessary log factor.

Map each element to its square and call a sort.

Time O(n log n)Space O(n)
Best choiceTwo pointers merging from the ends

Linear time using the sortedness; the intended solution.

Use the fact that largest magnitudes live at the extremes to place squares in order.

Time O(n)Space O(n)
The rule we keep true

Invariant

Every slot of result from position pos+1 to the end already holds the correct, sorted-largest squares, and the untaken elements nums[left..right] contain exactly the values whose squares still need placing.

Why this is correct

Reasoning

For a non-decreasing array, absolute values are largest at one or both ends and smallest somewhere in the middle. Whichever endpoint has greater magnitude has the greatest remaining square, so writing it to the current back of result and shrinking the window preserves descending placement. Filling from the back therefore yields a non-decreasing array when read front to back.

The algorithm in three movesSay these aloud before coding
1Allocate a result array of length n and put pointers at both ends of nums

|−4|=4 vs |10|=10 -> place 100 at index 4; right=3

2Compare abs(nums[left]) with abs(nums[right])

|−4|=4 vs |3|=3 -> place 16 at index 3; left=1

3Write the larger square into the current rightmost open slot

...continue -> 9, 1, 0 fill indices 2,1,0

4Move the pointer that supplied it inward and move the write position left

5Continue until all slots are filled

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
-40
-11
02
33
104
1 · Readnums[0]=-4, nums[4]=10
2 · AskWhich magnitude is larger?
3 · Update stateleft=0, right=4, pos=4
4 · Result|10| > |−4| -> result[4]=100; right=3.
Key takeaway

The largest magnitude (10 at the right) yields the largest square, placed at the end of the result first.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5Setup

    Preallocate the output and place pointers at both ends of the input.

  2. 2
    Lines 6Iterate write positions from the back

    pos counts down from n-1 to 0, so each iteration fills the next-largest square.

  3. 3
    Lines 7-12Pick the larger magnitude

    Square whichever endpoint is bigger in absolute value, write it at pos, and advance that pointer inward.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • All negative numbers (e.g. [-3,-2,-1]) — the most negative has the largest square, so left pointer drives the fill
  • All non-negative numbers — the right pointer drives the fill and squares are already in order
  • Single-element array — returned as its square
  • Presence of zero, whose square 0 is the minimum and lands at index 0
!

Common beginner mistakes

  • Comparing raw values instead of absolute values, which mishandles the negative side
  • Filling the result from the front, which requires the smallest square first and breaks the merge logic
  • Falling back to sorting the squares and losing the O(n) advantage the sorted input offers
Check your understanding

Why does the largest remaining square always sit at one of the two ends of the current window?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima