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].

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 reverses the order of the negative values, so the squares are not sorted. But the largest square always comes from one of the two ends of nums. Compare the 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. Sorting puts the squares in order no matter where they came from. The sort costs O(n log n) and ignores the order you were given.

Algorithm

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

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

Two pointers from both ends

Intuition

A square grows with the distance from 0. In a sorted array the values farthest from 0 sit at the two ends, the most negative on the left and the most positive on the right, so the largest square is nums[left]² or nums[right]². Write the larger one at the back of the result and move that pointer inward. What remains between the pointers is again sorted, so the same 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. 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

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.
Comparing nums[left] with nums[right] instead of their squares. -6 is smaller than 3, but its square is larger, so [-6, 3] comes out [36, 9].
Stopping when left meets right. One value is still unplaced; loop over every position, or use left <= right.
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 questions3

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.

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. Filling from the back avoids the search, because the ends are known from the start.

Is Squares of a Sorted Array a merge problem?

Yes. The negative values squared, read right to left, form one sorted list, 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.

def sortedSquares(nums):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output

[1, 4, 9, 36, 49]