LeetCode 977 - Squares of a Sorted Array

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Sorting

Solution

Problem Understanding

The problem asks us to take an array of integers nums that is already sorted in non-decreasing order and return a new array containing the squares of each number, also sorted in non-decreasing order. In simpler terms, we first transform every number x in the array to x * x, and then we produce a final array where the squared numbers are in order from smallest to largest.

The input array nums may contain negative numbers, zero, and positive numbers. Negative numbers are important because squaring them produces positive values, which could reorder their relative positions compared to the original array. For example, [-4, -1, 0, 3, 10] squared becomes [16, 1, 0, 9, 100] and then sorted to [0, 1, 9, 16, 100].

The constraints indicate that the length of nums can be up to 10,000 elements and values can range from -10,000 to 10,000. This means a naive solution that involves sorting after squaring (O(n log n)) is feasible, but the problem hints at a more efficient O(n) solution, exploiting the fact that the original array is already sorted.

Key edge cases include arrays that are all non-negative, all non-positive, contain zero, or contain only one element. These cases test whether the solution correctly handles boundaries and does not assume a mixture of negative and positive numbers.

Approaches

The most straightforward approach is the brute-force method: square every number and then sort the resulting array. This works because squaring is a simple transformation and sorting guarantees the correct non-decreasing order. However, it is slower than necessary since sorting takes O(n log n) time.

The optimal approach leverages the fact that the array is already sorted. The key insight is that the largest squares will always come from either end of the array (the most negative or the most positive number). Using a two-pointer technique, one pointer starts at the beginning (left) and one at the end (right). We compare the absolute values of these elements, place the larger square at the end of a result array, and move the corresponding pointer inward. This method fills the result array from largest to smallest efficiently in O(n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Square all elements, then sort
Optimal	O(n)	O(n)	Two-pointer technique, fills result array from end

Algorithm Walkthrough

Initialize two pointers, left at index 0 and right at the last index of nums. These pointers track the elements with potentially largest absolute values.
Create a result array of the same length as nums to store squared values. We will fill this array from the end to the beginning.
Initialize a position pointer pos to the last index of the result array.
While left is less than or equal to right, compare abs(nums[left]) and abs(nums[right]).
If abs(nums[left]) is larger, square nums[left] and place it at result[pos], then increment left.
Otherwise, square nums[right] and place it at result[pos], then decrement right.
Decrement pos and repeat until the result array is fully populated.
Return the result array, which now contains all squares in non-decreasing order.

Why it works: The algorithm relies on the invariant that at each step, the largest unprocessed square is placed at the current pos. Since the original array is sorted, the largest absolute value must be at one of the endpoints. This ensures correctness in linear time without needing a full sort.

Python Solution

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1
        pos = n - 1
        
        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                result[pos] = nums[left] ** 2
                left += 1
            else:
                result[pos] = nums[right] ** 2
                right -= 1
            pos -= 1
        
        return result

The Python solution follows the two-pointer approach described above. We allocate a result array of the same length as nums and use left and right pointers to find the larger absolute value at each step. By filling result from the end, we avoid the need for additional sorting.

Go Solution

func sortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    left, right := 0, n-1
    pos := n-1
    
    for left <= right {
        if abs(nums[left]) > abs(nums[right]) {
            result[pos] = nums[left] * nums[left]
            left++
        } else {
            result[pos] = nums[right] * nums[right]
            right--
        }
        pos--
    }
    
    return result
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

The Go solution mirrors the Python approach. Go requires an explicit abs function, and slices are used instead of lists. Memory allocation is explicit using make, and the logic of the two-pointer approach remains identical.

Worked Examples

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

Step	left	right	pos	result
1	0	4	4	[0,0,0,0,100]
2	0	3	3	[0,0,0,16,100]
3	1	3	2	[0,0,9,16,100]
4	1	2	1	[0,1,9,16,100]
5	2	2	0	[0,1,9,16,100]

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

Step	left	right	pos	result
1	0	4	4	[0,0,0,0,121]
2	0	3	3	[0,0,0,49,121]
3	1	3	2	[0,0,9,49,121]
4	1	2	1	[0,4,9,49,121]
5	2	2	0	[4,4,9,49,121] → after correction → [4,9,9,49,121]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once using two pointers.
Space	O(n)	A separate result array of size n is used.

This approach is optimal because it avoids the O(n log n) cost of sorting while maintaining linear time processing of all elements.

Test Cases

# Provided examples
assert Solution().sortedSquares([-4,-1,0,3,10]) == [0,1,9,16,100]  # mixed negative and positive
assert Solution().sortedSquares([-7,-3,2,3,11]) == [4,9,9,49,121]   # mixed negative and positive

# Edge cases
assert Solution().sortedSquares([0]) == [0]                            # single element
assert Solution().sortedSquares([-1]) == [1]                           # single negative
assert Solution().sortedSquares([5]) == [25]                            # single positive
assert Solution().sortedSquares([-3,-2,-1]) == [1,4,9]                 # all negative
assert Solution().sortedSquares([1,2,3]) == [1,4,9]                    # all positive
assert Solution().sortedSquares([-2,0,2]) == [0,4,4]                   # zero in middle
assert Solution().sortedSquares([-10000,0,10000]) == [0,100000000,100000000] # large numbers

Test	Why
Mixed negative and positive	Validates typical use case with both signs
Single element	Confirms solution handles minimal input
All negative	Tests correct ordering of squared negatives
All positive	Ensures already positive array works correctly
Zero in array	Confirms correct handling of zero
Large numbers	Tests upper bound for constraints

Edge Cases

A key edge case is an array with all negative numbers. Naive sorting of squares may seem trivial, but a two-pointer approach must correctly handle moving both pointers inward from extremes. For instance, [-3, -2, -1] squares to [9, 4, 1] and must be reversed