Squares of a Sorted Array

Easy Arrays & Hashing Two Pointer Original on LeetCode

Squares of a Sorted Array is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers from both ends), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (square then sort) up.

Problem

You are given an integer array nums sorted in non-decreasing order. Return a new array containing the square of every element, also sorted in non-decreasing order.

Can you do it in a single O(n) pass instead of squaring and sorting?

Examples

Example 1

Input
nums = [-6, -2, 0, 3, 5]
Output
[0, 4, 9, 25, 36]
Why
The squares are 36, 4, 0, 9, 25; sorted they become 0, 4, 9, 25, 36.

Example 2

Input
nums = [-9, -4, -1]
Output
[1, 16, 81]
Why
All values are negative, so the squares come out in reverse order.

Example 3

Input
nums = [-3, -3, 2, 3]
Output
[4, 9, 9, 9]
Why
Equal absolute values produce equal squares, and each one is kept.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in non-decreasing order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (square then sort)O(n log n)O(n)
Optimal (two pointers from both ends)O(n)O(n)

1Brute force (square then sort)

TimeO(n log n)The sort dominates.
SpaceO(n)The output array (plus the sort's own workspace).

Square every element into a new array and sort it.

  1. res[i] = nums[i] * nums[i] for every i.
  2. Sort res and return it.
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) res[i] = nums[i] * nums[i];
        Arrays.sort(res);
        return res;
    }
}

2Optimal (two pointers from both ends)

TimeO(n)Each element is placed exactly once.
SpaceO(n)Only the output array; O(1) extra beyond it.

The biggest square is at the left end (a large negative) or the right end. Compare the two ends, write the bigger square into the last free slot of the result, and move that pointer inward.

  1. lo = 0, hi = n - 1, pos = n - 1.
  2. While lo <= hi: if |nums[lo]| > |nums[hi]|, write nums[lo]² at pos and lo++; otherwise write nums[hi]² and hi--.
  3. Decrement pos each step and return the result.
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int lo = 0, hi = n - 1;
        for (int pos = n - 1; pos >= 0; pos--) {
            if (Math.abs(nums[lo]) > Math.abs(nums[hi])) {
                res[pos] = nums[lo] * nums[lo];
                lo++;
            } else {
                res[pos] = nums[hi] * nums[hi];
                hi--;
            }
        }
        return res;
    }
}

Edge cases to test

  • A single element
  • All negative (squares reverse the order) or all non-negative (order is kept)
  • Duplicates and values with the same absolute value on both sides of zero

Hints

Hint 1

Squaring breaks the order only because negative numbers flip. The largest square is always at one of the two ends.

Hint 2

Use two pointers at the ends and fill the result from the back with the larger of the two squares.

FAQ

What is the best time complexity for Squares of a Sorted Array?

Optimal (two pointers from both ends) runs in O(n) time and O(n) extra space. Each element is placed exactly once.

Which pattern does Squares of a Sorted Array use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Squares of a Sorted Array?

Yes. Brute force (square then sort) takes O(n log n) time and O(n) space. Square every element into a new array and sort it.

Which edge cases should I test for Squares of a Sorted Array?

A single element; All negative (squares reverse the order) or all non-negative (order is kept); Duplicates and values with the same absolute value on both sides of zero.