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
Example 1
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
Output: [4, 9, 9, 49, 121]
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.
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, lohihi
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
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
Choosing between the two ends
Which marker moves at each step? Square the number at lohihi
Why is the larger end square always the largest one left? Every number between lohilohi
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
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]
Java Solution
The method sortedSquares
- First, create
, a new array of the same lengthresult asn . The squares go there, sonums itself is not changed.nums - Put
on the first position, 0, andlo on the last,hi .n - 1 - Fill
with one loop that runs from the back:result starts atpos and goes down to 0. In each round,n - 1 is the square ofleft andnums[lo] is the square ofright .nums[hi] - If
is bigger, write it atleft and movepos right. Otherwise writelo atright and movepos left; this branch also handles a tie.hi - When the loop has filled slot 0, return
.result
The main
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:
[0, 1, 9, 16, 100]
[4, 9, 9, 49, 121]
[1, 4, 9]
[4, 4]
[25]
Example 1 gives [0, 1, 9, 16, 100][4, 9, 9, 49, 121]
Look at the third line: [-3, -2, -1][1, 4, 9]lohi
The fourth line, [4, 4][-2, 2]else[25]lohi
The original implementation,
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
, and each round does two multiplications and moves one marker.result - Space: O(n) for the result, O(1) besides it.
is the output itself; apart from it the method keeps onlyresult ,lo andhi .pos
Filling an array from the back is also how