Squares of a Sorted Array

Square every number of a sorted array and return the squares in sorted order, in one pass.

Given an integer array nums sorted in non-decreasing order, which means each number is at least as big as the one before it, return a new array with the square of every number. The new array must be sorted in non-decreasing order too.

Example 1
Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Explanation: the squares are [16, 1, 0, 9, 100], which sort to [0, 1, 9, 16, 100].
Example 2
Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Solution

The Idea

Squaring a number means multiplying it by itself: 3 squared is 9, and -4 squared is 16, because a negative times a negative is positive. Take Example 1, the numbers -4, -1, 0, 3 and 10, which go up from left to right. Square each one where it stands and you get 16, 1, 0, 9 and 100, which no longer go up.

What broke the order? -4 is smaller than 3, but its square, 16, is bigger than 9. A square ignores the sign and depends only on how far the number is from 0. Among the negative numbers, the further left a number sits, the further it is from 0. So the squares of the negative numbers grow towards the left end, and the squares of the positive numbers grow towards the right end.

Look at the picture below. The row labelled nums is the input. Under each number, a bar shows how far it is from 0, with the square on top. The bars form a valley: big at both ends, smallest near 0 in the middle.

The sorted array -4, -1, 0, 3, 10 with lo on -4 and hi on 10. Their squares 16, 1, 0, 9, 100 are big at both ends and smallest near 0 in the middle. The larger end square, 100, is written into the last slot of result first, then 16 into the slot before it.

So where is the largest square? It must be at one of the two ends, here 16 on the left or 100 on the right. Put one marker, lo, on the first number and another, hi, on the last. Their squares are 16 and 100. The bigger one, 100, is the largest square of all, so it goes into the last slot of the row labelled result, marked "written 1st". Then hi moves one step left, onto 3.

Now the two ends are -4 and 3, and the largest square left must again be at one of them. The larger of 16 and 9 is the largest square left, so 16 goes into the slot before 100, marked "written 2nd", and lo moves right. Each comparison places one square, from the largest down, so the result fills from right to left.

Moving two markers from the two ends of an array towards each other is called the two-pointer technique. Here each step places one number for good, and the markers never move back, so one pass over the array is enough.

Solution Approach

Turning that idea into code means settling three things: whether to sort at all, which end to take at each step, and where in the result each square goes.

Squaring, then sorting

What is the simplest way? Square every number into a new array and sort it with Arrays.sort. That works, but sorting n numbers takes O(n log n) time, which grows a little faster than n itself. It also throws away the fact that the input is already sorted. The two markers use that order and need only one step per number, O(n).

Choosing between the two ends

Which marker moves at each step? Square the number at lo and the number at hi, write the larger square into the result, and move only that marker inward. When both squares are equal, as with -2 and 2, either can go first. The code takes the one at hi, and the other copy comes in the next step.

Why is the larger end square always the largest one left? Every number between lo and hi is either a negative number closer to 0 than the one at lo, or a positive number closer to 0 than the one at hi. Its square is therefore no bigger than one of the two end squares.

Filling the result from the back

Why not start with the smallest square and fill from the front? The smallest square belongs to the number closest to 0, and that number can sit anywhere in the middle, like the 0 in Example 1. Comparing the two ends only ever finds the largest square. So the result is filled at a position pos that starts at the last slot and moves one step left each time.

Taking the smaller end square and filling from the front does not work. Run on Example 1, that version returns [16, 1, 0, 9, 100], the squares in their original, unsorted order.

Java Solution

The method sortedSquares works in these steps:

  1. First, create result, a new array of the same length n as nums. The squares go there, so nums itself is not changed.
  2. Put lo on the first position, 0, and hi on the last, n - 1.
  3. Fill result with one loop that runs from the back: pos starts at n - 1 and goes down to 0. In each round, left is the square of nums[lo] and right is the square of nums[hi].
  4. If left is bigger, write it at pos and move lo right. Otherwise write right at pos and move hi left; this branch also handles a tie.
  5. When the loop has filled slot 0, return result.

The main method runs both examples, an array of only negative numbers, two numbers with the same square, and an array of a single number.

Java
import java.util.Arrays;

public class SquaresOfSortedArray {

    public static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int lo = 0;
        int hi = n - 1;
        for (int pos = n - 1; pos >= 0; pos--) {   // fill from the largest square down
            int left = nums[lo] * nums[lo];
            int right = nums[hi] * nums[hi];
            if (left > right) {
                result[pos] = left;
                lo++;
            } else {
                result[pos] = right;
                hi--;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(sortedSquares(new int[] {-4, -1, 0, 3, 10})));
        System.out.println(Arrays.toString(sortedSquares(new int[] {-7, -3, 2, 3, 11})));
        System.out.println(Arrays.toString(sortedSquares(new int[] {-3, -2, -1})));
        System.out.println(Arrays.toString(sortedSquares(new int[] {-2, 2})));
        System.out.println(Arrays.toString(sortedSquares(new int[] {5})));
    }
}

Running it prints:

Output
[0, 1, 9, 16, 100]
[4, 9, 9, 49, 121]
[1, 4, 9]
[4, 4]
[25]

Example 1 gives [0, 1, 9, 16, 100], and Example 2 gives [4, 9, 9, 49, 121], where -3 and 3 both square to 9 and both copies appear.

Look at the third line: [-3, -2, -1] gives [1, 4, 9]. Every number is negative, so the largest square is at lo each time, and hi stays on -1 until the last round. The squares come out in the reverse of the input order.

The fourth line, [4, 4], comes from [-2, 2]. Both ends give 4, so the else branch writes the square of 2 into the last slot, and the next round writes the square of -2 before it. The last line, [25], shows a single number: lo and hi both start on 5, and the loop runs once.

The original implementation, SquaresOfSortedArray.java, is on GitHub.

Complexity

The work is one pass that fills the result, with no sort.

  • Time: O(n), because the loop runs once for each of the n slots of result, and each round does two multiplications and moves one marker.
  • Space: O(n) for the result, O(1) besides it. result is the output itself; apart from it the method keeps only lo, hi and pos.

Filling an array from the back is also how Merge Sorted Array merges two sorted arrays in place.