Squares of a Sorted Array

Q: What is the time complexity of Squares of a Sorted Array?

The two pointer solution runs in O(n) time: each value is squared and placed once. Squaring and then sorting costs O(n log n) . Both use O(n) memory for the result.

EasyTwo pointers Sorting

+10

You get an array of integers nums sorted in non-decreasing order. It may hold negative values. Square every value and return the squares as a new array, also sorted in non-decreasing order.

Function

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: the sorted array of integers, negatives allowed
Returnsinteger-array: the square of every value, sorted in non-decreasing order

Constraints

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in non-decreasing order.

Examples

Input: nums = [-6, -2, 1, 3, 7]
Output: [1, 4, 9, 36, 49]
Explanation: The squares in the original order are 36, 4, 1, 9 and 49. The negative values -6 and -2 give large squares, so sorting moves 36 near the end: [1, 4, 9, 36, 49].

Input: nums = [-9, -4, -1]
Output: [1, 16, 81]
Explanation: Every value is negative, so the squares come out in reverse: 81, 16, 1 becomes [1, 16, 81].

+14 hidden tests on Submit

Follow-up

Squaring and sorting takes O(n log n). Can you do it in O(n)?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Squaring keeps the order of the non-negative values but reverses the order of the negative ones, so the squares are not sorted. Sorting them again works but ignores the order you were given. The key fact: the largest square always comes from one of the two ends of nums. Compare the two ends, place the larger square at the back of the result, and move inward.

Square, then sort

Intuition

Build a new array with the square of every value, then sort it. Squares are never negative, and sorting puts them in order no matter where they came from.

For [-6, -2, 1, 3, 7] the squares are [36, 4, 1, 9, 49], and sorting gives [1, 4, 9, 36, 49].

The sort costs O(n log n). That is fast enough here, but it treats the input as if it had no order at all. The next approach uses the order and needs one pass.

Algorithm

Create an array with x * x for every x in nums.
Sort it in increasing numeric order.
Return it.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Two pointers from both ends

Intuition

Think of the squares as the distance from 0, squared. In a sorted array the values farthest from 0 sit at the two ends: the most negative value on the left and the most positive on the right. So the largest square is nums[left]² or nums[right]², never anything in between.

Keep left at 0 and right at n-1, and fill the result from its last position backward. Each step, compare the two end squares, write the larger one at the current position and move that pointer inward. What is left between the pointers is again a sorted array, so the same fact holds at every step.

On [-6, -2, 1, 3, 7]: 49 beats 36 and goes last. Then 36 beats 9, 9 beats 4, 4 beats 1, and the 1 fills position 0. The result is [1, 4, 9, 36, 49]. Every value is placed once: O(n) time, and the result is the only extra array.

Algorithm

Create a result array of length n. Set left to 0 and right to n-1.
Walk a position pos from n-1 down to 0.
Compare nums[left]² with nums[right]².
Write the larger square at pos and move that pointer one step inward.
Return the result.

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    # the largest square left is always at one of the two ends
    for pos in range(n - 1, -1, -1):
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
    return result

Pitfalls and edge cases

The two pointer version is short, but a few details break it.

Filling the result from the front. The smallest square sits where the values cross 0, which can be anywhere in the middle. The ends only tell you the largest square. Fill from the back.
Comparing nums[left] with nums[right] instead of their squares or absolute values. -6 is smaller than 3, but its square is larger.
Stopping when left meets right. When they are equal, one value is still unplaced; loop over every position of the result, or use left <= right.
All negative or all positive input. With [-9, -4, -1] the left pointer does all the work, and with [2, 5, 8] the right one does. Both must still give sorted output.
In JavaScript and TypeScript, sort() without a comparator sorts numbers as text, so [1, 4, 36, 9] becomes [1, 36, 4, 9]. Pass (a, b) => a - b.

Frequently asked questions4

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

The two pointer solution runs in O(n) time: each value is squared and placed once. Squaring and then sorting costs O(n log n). Both use O(n) memory for the result.

Why does the largest square come from one of the two ends?

A square grows with the distance from 0. In a sorted array the value farthest below 0 is the first one, and the value farthest above 0 is the last one. Every value in between is closer to 0 than one of them, so its square cannot be the largest.

Can you fill the result from the front instead?

Yes, but you first have to find where the values cross 0, for example with a binary search. Then two pointers walk outward from that point, like merging two sorted lists: the negatives read right to left and the non-negatives left to right. Filling from the back avoids the search, because the ends are known from the start.

Is Squares of a Sorted Array a merge problem?

In disguise, yes. The negative values squared form one sorted list (read from right to left), and the non-negative values squared form another. Combining them is the merge step of merge sort, which is why it fits in one linear pass.

Python

def sortedSquares(nums):
    # Write code here

Test cases

Case 1

Case 2

Input

nums = [-6, -2, 1, 3, 7]

Expected

[1, 4, 9, 36, 49]