Squares of a Sorted Array

Problem Overview

Given an array sorted in non-decreasing order (which may include negative numbers), return a new array of the squares of each number, also sorted in non-decreasing order.

Why solve this?

A clean first example of converging two pointers on a sorted array where the two ends — not just one — are both meaningful, because squaring negatives can make them the largest values in the result.

Pattern Recognition

Whenever a sorted array's values get transformed by something that isn't order-preserving (like squaring, which flips the relative order of negatives), consider comparing from both ends inward instead of scanning left to right.

Prerequisites

• Comfort with converging two-pointer traversal on a sorted array.

Hints

1. The largest square in the result always comes from whichever end — leftmost or rightmost — has the larger absolute value.
2. Fill the answer array from the back (largest value first), shrinking whichever pointer produced the larger square.
3. You never need to sort the output afterward if you build it back-to-front this way.

Approach

Compare the absolute values at the left and right ends of the array with two pointers. Whichever end has the larger absolute value produces the larger square, and since the array is sorted, that must be the largest remaining square overall — so it belongs at the back of the result. Fill the result array from its last index down to its first: at each step, square whichever end (left or right) has the larger absolute value, place it at the current back position, and move that pointer inward. This avoids any post-hoc sort because the result is constructed in final sorted order directly.

Code

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        for (int idx = n - 1; idx >= 0; idx--) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[idx] = nums[left] * nums[left];
                left++;
            } else {
                result[idx] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy