Squares of a Sorted Array
Squares of a Sorted Array is a classic two-pointer problem that tests whether you can take advantage of sorted input instead of doing extra work. You are given an array of integers sorted in non-decreasing order. The values can be negative, zero, or positive.
Your task is to return a new array containing the squares of each number, also sorted in non-decreasing order.
This seems simple at first because squaring is straightforward. The catch is that squaring changes ordering when negative numbers are involved. A large negative value becomes a large positive square, which can end up bigger than the square of a smaller positive value.
For example, [-4, -1, 0, 3, 10] becomes [16, 1, 0, 9, 100] before sorting, and you need the final result to be [0, 1, 9, 16, 100].
Interviewers like this question because it looks like it could be solved by squaring everything and sorting again, but they want you to recognize a faster, cleaner approach.
Why “square then sort” is not ideal
If you square every value and then sort the result, you will get the correct answer. But sorting adds extra cost.
Since the input is already sorted, the problem is nudging you toward a solution that runs in linear time. That usually means using pointers and exploiting structure.
The main insight is that the largest square will come from one of the ends of the array. Either the most negative number or the most positive number will have the largest absolute value, and squaring turns absolute value into size.
The key idea behind the solution
The array is sorted by value, but not by absolute value.
Negative values on the left can have large magnitude, and positive values on the right can also have large magnitude. The middle values tend to have a smaller magnitude.
So the largest squared values will appear near the ends, not necessarily at the right side, as they would in a fully non-negative array.
This leads to a two-pointer approach where you compare absolute values at both ends and place the larger square into the result.
Want to explore more coding problem solutions? Check out the Delete Node in a Linked List and Number of Dice Rolls With Target Sum.
How the two-pointer approach works conceptually
You start with two pointers.
One pointer begins at the left end of the array. The other begins at the right end.
You also build a result array of the same size. Instead of filling it from left to right, you fill it from right to left, because you can identify the largest squares first.
At each step, you compare the absolute value of the number at the left pointer with the absolute value of the number at the right pointer.
If the left absolute value is larger, then its square is larger, and that square belongs at the current back position in the result. You place it there and move the left pointer inward.
If the right absolute value is larger than or equal to, you place the square from the right side into the result and move the right pointer inward.
You repeat until the pointers cross and the result array is fully filled.
Why this approach works
This works because you are effectively merging two sorted sequences.
If you look at the input array, the negative side becomes increasing in square values when read from right to left, because the magnitudes shrink as you approach zero.
The positive side becomes increasing in square values when read from left to right.
The two-pointer method merges these two square sequences by always selecting the largest remaining square and placing it at the end of the result.
You never need to sort because you’re building the sorted output directly.
Performance in simple terms
The array is scanned once from both ends, so the time complexity is linear in the number of elements.
The extra space used is the result array itself, which is required by the output.
This is the efficient solution interviewers expect.
Top comments (0)