Squares of a Sorted Array
Square every value in a sorted array and return the squares in sorted order. Tests whether you see that the largest squares sit at the two ends, so two pointers beat re-sorting. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an integer array nums sorted in non-decreasing order. It may contain negative numbers.
Return a new array holding the square of every element, also sorted in non-decreasing order.
Example 1
- Input
- nums = [-6, -2, 0, 3, 5]
- Output
- [0, 4, 9, 25, 36]
The squares are [36, 4, 0, 9, 25]. Sorted, that is [0, 4, 9, 25, 36].
Example 2
- Input
- nums = [-3, -3, 1, 2]
- Output
- [1, 4, 9, 9]
Example 3
- Input
- nums = [1, 4, 7]
- Output
- [1, 16, 49]
With no negatives, squaring keeps the order.
Constraints
- 1 ≤ nums.length ≤ 10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- nums is sorted in non-decreasing order.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Squares of a Sorted Array in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Squares of a Sorted Array
Pattern: Two pointers from both ends
Squaring breaks the order only because of the negatives: -6 is the smallest value but 36 is one of the largest squares. Look at where the big squares can be, though. The largest absolute value is always at one of the two ends of a sorted array, either the most negative number on the left or the most positive on the right.
So compare the two ends, take the one with the larger square, and write it into the last open slot of the result. Move that pointer inward and repeat. You fill the answer from the back, biggest first, in a single pass.
Approach 1: Square, then sort
Square every element and call the built-in sort. Short and correct, but it ignores that the input was already sorted and pays O(n log n) for it.
Time O(n log n) · Space O(n)
Approach 2: Split at zero and merge
Find the first non-negative index. The negatives, read right to left, give increasing squares; the non-negatives, read left to right, do too. Merge the two runs like merge sort. Linear, but finding the split point and walking outward from it adds boundary cases.
Time O(n) · Space O(n)
Approach 3: Two pointers filling from the back
Set left = 0, right = n - 1, and pos = n - 1. While left <= right:
- Compare
nums[left]²andnums[right]². - Write the larger one to
result[pos], move that pointer inward, and decrementpos.
Each step places the largest remaining square, so the result comes out sorted.
Time O(n) · Space O(n) for the output
| Approach | Time | Space |
|---|---|---|
| Square, then sort | O(n log n) | O(n) |
| Split at zero and merge | O(n) | O(n) |
| Two pointers filling from the back | O(n) | O(n) for the output |
Solution code
Try the practice editor first. Both solutions pass every test above.
Squares of a Sorted Array solution in Python
def sorted_squares(nums: list[int]) -> list[int]:
n = len(nums)
result = [0] * n
left, right = 0, n - 1
for pos in range(n - 1, -1, -1): # fill from the back, largest first
if abs(nums[left]) > abs(nums[right]):
result[pos] = nums[left] * nums[left]
left += 1
else:
result[pos] = nums[right] * nums[right]
right -= 1
return resultSquares of a Sorted Array solution in JavaScript
function sortedSquares(nums) {
const n = nums.length;
const result = new Array(n);
let left = 0;
let right = n - 1;
for (let pos = n - 1; pos >= 0; pos--) {
// fill from the back, largest first
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
result[pos] = nums[left] * nums[left];
left++;
} else {
result[pos] = nums[right] * nums[right];
right--;
}
}
return result;
}Common mistakes
- Filling the result from the front. The ends hold the largest squares, not the smallest, so the front is where you know the least.
- Using `left < right` as the loop condition and dropping the last remaining element.
- Assuming the array has both negatives and positives. All-negative and all-positive inputs must work too.
- Comparing the raw values instead of their squares or absolute values, which picks the wrong end when negatives are involved.
What interviewers look for
Give the square-and-sort answer first and name its cost, then ask yourself what the sorted input buys you. The sentence interviewers want is "the largest square is always at one of the ends." Once you say that, the two-pointer fill is easy to justify.
Walk through an all-negative case like [-9, -5, -1] to show the right pointer never moves until the left side is used up.
Follow-up questions
Can you do it without the split-at-zero bookkeeping?
Yes. Filling from the back with two pointers never needs to find zero, because the larger square is always at one of the ends. That is why it is the usual answer.
What if you had to return the result in decreasing order?
Use the same loop but write to the front of the result, from index 0 upward. You still pick the larger end each time.
What if the transform were any function, like x² + 3x?
Two pointers work whenever the function is convex (or concave): its largest values on a sorted input are still at the ends. For a quadratic ax² + bx + c with a > 0, fill from the back; with a < 0, the largest values are in the middle, so fill from the front by taking the smaller end.
Companies that ask Squares of a Sorted Array
Squares of a Sorted Array is tagged by 107 companies in our interview dataset. The score shows how often it comes up at each company.
- Caterpillar100%
- Verisk100%
- Nortonlifelock100%
- State Farm100%
- 1password97%
- Clevertap93%
- Instacart92.1%
- Binance90%
- Clear Street90%
- Saif90%
- 2u88%
- Alto88%
- Hinge88%
- And Digital87%
- Testlio86%
- Uber85.8%
- N2684%
- Wisetech Global84%
- Global Relay84%
- Nuance Communications82%
- Biontech81%
- Cerner81%
- Atos81%
- Gigamon80%
and 83 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required