Squares of a Sorted Array
Return the sorted squares of a sorted array in O(n): the largest square is always at one end, so fill the output from the back with two pointers.
Problem Understanding
Squares of a Sorted Array: given an array sorted in non-decreasing order, return the squares of each number, also sorted.
Example: [-4, -1, 0, 3, 10] returns [0, 1, 9, 16, 100]. Squaring in place gives [16, 1, 0, 9, 100], which is no longer sorted because of the negatives.
The Intuition: The Biggest Square Is on the Outside
Negatives break the order: -4 is smaller than 3, but its square is larger. What stays true is that squares grow with absolute value, and in a sorted array the largest absolute values sit at the two ends.
So use two pointers, one at each end, and build the answer from the largest square down:
- Compare
|nums[lo]|and|nums[hi]|. - Write the larger one's square to the last free slot of the output.
- Move that pointer inward and repeat.
It is the same back-to-front fill as Merge Sorted Array: two sorted runs (the negatives reversed, and the positives) merged from the largest end.
Interactive Walkthrough
The values still between lo and hi are shaded. Each step, the end with the larger absolute value wins: its square drops into the output at k, which fills from the right.
Dry Run Table
Input: [-4, -1, 0, 3, 10]
| lo | hi | Compare | Write | k |
|---|---|---|---|---|
| -4 | 10 | 4 < 10 | 100 | 4 |
| -4 | 3 | 4 > 3 | 16 | 3 |
| -1 | 3 | 1 < 3 | 9 | 2 |
| -1 | 0 | 1 > 0 | 1 | 1 |
| 0 | 0 | equal | 0 | 0 |
Result: [0, 1, 9, 16, 100].
The Solution Template
Two pointers from the ends, filling the output from the back.
Squares of a Sorted Array Code
1var sortedSquares = function(nums) {2 const n = nums.length;3 const out = new Array(n);4 let lo = 0, hi = n - 1;5 for (let k = n - 1; k >= 0; k--) {6 if (Math.abs(nums[lo]) > Math.abs(nums[hi])) {7 out[k] = nums[lo] * nums[lo];8 lo++;9 } else {10 out[k] = nums[hi] * nums[hi];11 hi--;12 }13 }14 return out;15};
Edge Cases & Common Mistakes
- All non-negative: the right end always wins; the squares keep their order.
- All negative: the left end always wins; the output is the input reversed and squared.
- Filling from the front: the ends give the largest squares, so writing them at the front produces a descending array.
- Comparing values instead of absolute values:
-4 < 3, but16 > 9.
Summary
Squares grow with absolute value, so the largest square left is always at one end of the sorted array. Compare the two ends, write the larger square into the output from the back, and move that pointer inward. O(n) time.
More practice: DSA interview questions with answers · patterns cheat sheet