Squares of a Sorted Array

Given an array sorted in non-decreasing order, return an array of the squares of each number, also sorted. The obvious solution squares everything and sorts, at O(n log n). The linear solution rests on one observation: the largest square is always at one end of the array, never in the middle.

Written against Java 17.

The problem

Input:  [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]

Input:  [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]

The input is sorted; the squares are not, because squaring folds the negative half back over the positive one. -4 squares to 16, which belongs after 9.

The obvious solution

static int[] sortedSquares(int[] nums) {
    int[] result = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        result[i] = nums[i] * nums[i];
    }
    Arrays.sort(result);
    return result;
}

Correct, three lines, O(n log n). It throws away the fact that the input was sorted, which is the information that makes a linear solution possible.

Worth writing first anyway: it is the reference the fast version is tested against.

Two pointers, filling backwards

static int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0, right = n - 1;

    for (int write = n - 1; write >= 0; write--) {
        int leftSquare = nums[left] * nums[left];
        int rightSquare = nums[right] * nums[right];

        if (leftSquare > rightSquare) {
            result[write] = leftSquare;
            left++;
        } else {
            result[write] = rightSquare;
            right--;
        }
    }
    return result;
}

O(n) time, O(n) space for the output and O(1) beyond it.

Why the largest is at an end

The input is sorted, so the most negative value is at the left end and the most positive at the right. Squaring maps both away from zero, so the largest square is the square of whichever end has the greater absolute value. Nothing in the middle can beat both ends, because everything in the middle is closer to zero than at least one of them.

That is the whole argument, and it holds after every step: removing one end leaves a shorter sorted array with the same property.

Why fill backwards

Because the comparison identifies the largest remaining square, not the smallest. Writing it into the last unfilled position and moving inward means each value is placed in its final slot the moment it is chosen.

Filling forwards would require identifying the smallest remaining square, which is not at either end. It is wherever the array crosses zero, and finding it is another search. That asymmetry is why the backwards loop is not a stylistic choice.

An alternative forwards version does exist: find the crossing point by binary search, then merge the two halves outward: one descending through the negatives, one ascending through the positives. It is the same O(n) with more code and more places to get an index wrong.

Tracing it

nums = [-4, -1, 0, 3, 10]:

write	left	right	left²	right²	chosen	result so far
4	0	4	16	100	100	[_, _, _, _, 100]
3	0	3	16	9	16	[_, _, _, 16, 100]
2	1	3	1	9	9	[_, _, 9, 16, 100]
1	1	2	1	0	1	[_, 1, 9, 16, 100]
0	2	2	0	0	0	[0, 1, 9, 16, 100]

The last row is the case worth noting: left == right, both squares are the same element, and the else branch takes it once. Either branch would be correct there — what matters is that exactly one pointer moves, so the loop terminates.

The comparison, and the tie

if (leftSquare > rightSquare) — strictly greater, with the tie going to the right.

On [-3, 3] both squares are 9. Either branch produces the correct output, because the values are equal; the only requirement is that one pointer moves per iteration, which both branches satisfy.

Using >= instead is equally correct here. It is worth knowing why — in problems where the two sides carry different payloads, the tie-break decides which one is emitted first and stability matters. Here it does not.

Overflow

int leftSquare = nums[left] * nums[left];

This overflows when |nums[i]| > 46,340, because 46,341² exceeds Integer.MAX_VALUE. The result wraps to a negative number, the comparison takes the wrong branch, and the output is silently wrong — no exception.

If the input range permits large values:

long leftSquare = (long) nums[left] * nums[left];

and the result array becomes long[]. The cast must be on an operand, not on the product — (long) (a * a) overflows first and then widens the wrong answer, which is a distinct and equally silent bug.

Most statements of this problem bound the values to ±10⁴, where int is safe. That bound is a promise from the problem setter, not a property of the algorithm.

Edge cases

• All negative — [-5, -3, -1] gives [1, 9, 25]. The left pointer wins every comparison and walks the whole array.
• All positive — the right pointer walks the whole array.
• A single element — one iteration, left == right.
• Zeros — 0 * 0 is 0 and sorts first; no special handling.
• Empty array — the loop does not run and an empty array is returned, which is correct.

Only the empty case needs no guard, and it is the one people add a guard for.

Can it be done in place?

Not in the general case, and the reason is instructive.

Writing a square into nums[write] destroys a value that has not been read yet. On [-4, -1, 0, 3, 10], the first step writes 100 into index 4 — which held the 10 that produced it, so that one is safe. The second writes 16 into index 3, destroying the 3 whose square is still needed.

An in-place version therefore has to read both pointers before writing, and the write position collides with the unread region as soon as the left pointer wins more often than the right. There is no ordering that avoids it.

The O(1)-space variant that does exist squares everything in place first — which is safe, since each square depends only on its own cell — and then sorts:

for (int i = 0; i < nums.length; i++) nums[i] *= nums[i];
Arrays.sort(nums);

That is O(n log n) time and genuinely O(1) extra space, which is the right trade only when memory is the binding constraint. The linear version’s O(n) output array is usually cheaper than the log factor.

The transferable move

Two pointers from the outside in, filling the result from the back, is the shape for any problem where the extreme values sit at the ends of a sorted input and the ordering is disturbed by a monotone transformation applied around a centre.

The same structure merges two sorted arrays in place when the destination has room at the end, which is why “merge sorted array” and this problem feel alike: both write backwards precisely because writing forwards would overwrite input that has not been read yet.

More in the algorithms guides, including binary search for the crossing-point variant.

Frequently asked questions

Why not just square and sort?

It works and costs O(n log n). It also discards the fact that the input was sorted, which is exactly the information that allows O(n).

Why is the largest square always at one end?

The input is sorted, so the extremes of magnitude are at the ends. Squaring maps both away from zero, and nothing in the middle exceeds both ends.

Why fill the result backwards?

The comparison finds the largest remaining square, so it belongs in the last unfilled slot. The smallest is not at either end, so a forwards fill would need a separate search.

What is the time complexity?

O(n), with O(n) for the output and O(1) additional space.

Does it matter which branch handles a tie?

Not here — the values are equal. What matters is that exactly one pointer moves per iteration so the loop terminates.

Can the squares overflow?

Yes, above about 46,340 in absolute value. The wrap is negative, the comparison goes the wrong way, and the output is silently wrong. Use long if the range allows it.

Where does the long cast go?

On an operand: (long) a * a. Casting the product overflows first and then widens the wrong value.

What if the array is all negative?

The left pointer wins every comparison and traverses the array. No special case is needed.

What about an empty array?

The loop body never runs and an empty result is returned, which is correct without a guard.

Is there a forwards version?

Yes — binary search for the zero crossing, then merge outward. Same complexity, more code, more index errors.