Problem 6.4 · Two PointersEasy

Squares of a Sorted Array

What it teaches: The largest squares sit at the two ends; fill the result from the back by comparing ends.

Practise it on judges as “Squares of a Sorted Array”.

The problem

Given a sorted array nums (possibly with negatives), return an array of the squares of each number, sorted in non-decreasing order.

Example 1

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

Example 2

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

Constraints

1 ≤ nums.length ≤ 10⁴
Sorted
O(n) wanted

Pattern clues in the wording

→ Sorted input whose transformed order isn't sorted
→ Biggest values are at the ends

These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] out = new int[nums.length];
        return out;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [-4,-1,0,3,10]	[0,1,9,16,100]
2	nums = [-7,-3,2,3,11]	[4,9,9,49,121]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Square and sort · O(n log n)2. Optimal: compare the ends, fill from the back · O(n)

Square and sort

Time O(n log n) Space O(n)

Square every element, then sort.

Approach 1

import java.util.Arrays;

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] out = new int[nums.length];
        for (int i = 0; i < nums.length; i++) out[i] = nums[i] * nums[i];
        Arrays.sort(out);
        return out;
    }
}

Verdict: Fine, but ignores that the input is already sorted.

Optimal: compare the ends, fill from the back

Time O(n) Space O(n) for the output

The largest absolute value is at one of the two ends. Compare |nums[L]| and |nums[R]|, write the bigger square at the end of the output, and move that pointer inwards.

▶ Dry run: Largest squares firstnums = [-4, -1, 0, 3, 10]

-4

↑L

-1

↑R

out (from the back)(list)

____100

Step 1/4|−4| vs |10|: 10 wins. Write 100 last; R moves.

Approach 2

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] out = new int[n];
        int L = 0, R = n - 1;
        for (int k = n - 1; k >= 0; k--) {
            if (Math.abs(nums[L]) > Math.abs(nums[R])) {
                out[k] = nums[L] * nums[L];
                L++;
            } else {
                out[k] = nums[R] * nums[R];
                R--;
            }
        }
        return out;
    }
}

Verdict: One pass using the sorted input.

Before you submit

Edge cases and common mistakes

Test these inputs

All negative
All non-negative
One element

Mistakes people make

Filling from the front (the smallest square is in the middle, hard to find).

Interview

Follow-up questions

What if you needed the squares in decreasing order?

Command Palette