LeetCode 977: Squares of a Sorted Array

Problem Restatement

We are given an integer array nums sorted in non-decreasing order.

We need to return a new array containing the square of each number, also sorted in non-decreasing order.

The difficulty comes from negative numbers.

For example:

nums = [-4, -1, 0, 3, 10]

If we square each value in the same order, we get:

[16, 1, 0, 9, 100]

This result is not sorted.

The official constraints are 1 <= nums.length <= 10^4, -10^4 <= nums[i] <= 10^4, and nums is sorted in non-decreasing order. The follow-up asks for an O(n) solution.

Input and Output

Function shape:

def sortedSquares(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [-4, -1, 0, 3, 10]

Squaring each value gives:

[16, 1, 0, 9, 100]

After sorting:

[0, 1, 9, 16, 100]

Answer:

[0, 1, 9, 16, 100]

Example 2:

nums = [-7, -3, 2, 3, 11]

The squared values are:

[49, 9, 4, 9, 121]

Sorted result:

[4, 9, 9, 49, 121]

Answer:

[4, 9, 9, 49, 121]

First Thought: Square Then Sort

The simplest solution is to square every number, then sort the result.

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        squares = []

        for num in nums:
            squares.append(num * num)

        squares.sort()
        return squares

This is easy to write and easy to understand.

It works because sorting fixes the order after squaring.

Problem With Sorting Again

The array is already sorted.

Sorting the squared values costs:

O(n log n)

The follow-up asks for an O(n) solution, so we should use the sorted structure of the input instead of sorting again.

Key Insight

The largest square must come from one of the two ends of the array.

Why?

Because nums is sorted.

The left end may contain the most negative number.

The right end contains the largest positive number.

After squaring, a large negative value can become very large.

For example:

-7 * -7 = 49
11 * 11 = 121

So at each step, compare the absolute values at both ends:

abs(nums[left]) and abs(nums[right])

Whichever side has the larger absolute value produces the larger square.

We can fill the answer array from right to left.

Algorithm

Create an answer array of the same length as nums.

Use three pointers:

At each step:

1. Compare abs(nums[left]) and abs(nums[right]).
2. Put the larger square at answer[pos].
3. Move the pointer that was used.
4. Move pos one step left.

Because we fill from the end, the largest squares are placed first, and the final array remains sorted.

Correctness

The input array is sorted in non-decreasing order.

At any point, all unused numbers are between left and right.

The largest square among the unused numbers must come from either nums[left] or nums[right].

This is because the largest absolute value in a sorted interval is always at one of the two ends.

The algorithm compares these two values and writes the larger square into the last unfilled position of the answer array.

So each step places the largest remaining square into its final correct position.

After placing it, the corresponding pointer moves inward, removing that value from future consideration.

By repeating this process until all positions are filled, every squared value is placed in sorted order.

Therefore, the returned array is correct.

Complexity

Implementation

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [0] * n

        left = 0
        right = n - 1
        pos = n - 1

        while left <= right:
            left_square = nums[left] * nums[left]
            right_square = nums[right] * nums[right]

            if left_square > right_square:
                answer[pos] = left_square
                left += 1
            else:
                answer[pos] = right_square
                right -= 1

            pos -= 1

        return answer

Code Explanation

We create an output array:

answer = [0] * n

This lets us place values directly into their final position.

We start one pointer at the left end and one pointer at the right end:

left = 0
right = n - 1

The next largest square should go at the end of answer:

pos = n - 1

The loop continues while there are still unused values:

while left <= right:

At each step, square both candidates:

left_square = nums[left] * nums[left]
right_square = nums[right] * nums[right]

If the left square is larger, place it at answer[pos]:

answer[pos] = left_square
left += 1

Otherwise, place the right square:

answer[pos] = right_square
right -= 1

Then move pos left:

pos -= 1

When the loop ends, all squares have been placed in sorted order.

Testing

def run_tests():
    s = Solution()

    assert s.sortedSquares([-4, -1, 0, 3, 10]) == [0, 1, 9, 16, 100]
    assert s.sortedSquares([-7, -3, 2, 3, 11]) == [4, 9, 9, 49, 121]
    assert s.sortedSquares([1, 2, 3]) == [1, 4, 9]
    assert s.sortedSquares([-3, -2, -1]) == [1, 4, 9]
    assert s.sortedSquares([0]) == [0]
    assert s.sortedSquares([-2, 0, 2]) == [0, 4, 4]

    print("all tests passed")

run_tests()