977. Squares of a Sorted ArrayEasy

Squares of a Sorted Array

EasyArrayTwo PointersSorting·GoogleAmazon

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

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

Output:[0,1,9,16,100]

After squaring: [16,1,0,9,100]. After sorting: [0,1,9,16,100].

Example 2:

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

Output:[4,9,9,49,121]

Constraints:

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

Hints

Hint 1The input is sorted, so the largest squares must come from either end.▼

Since the array is sorted, the most negative numbers are at the left and the most positive at the right. Squaring flips negatives, so the largest square must come from one of the two ends — either the most negative element (left) or the most positive (right). A brute-force approach of squaring then sorting takes O(n log n). The two-pointer approach uses this observation to build the result in O(n).

Hint 2Use two pointers at both ends and always place the larger square at the current rightmost unfilled position.▼

Maintain l=0, r=n-1, and pos=n-1. Compare abs(nums[l]) vs abs(nums[r]). Whichever is larger — square it and place it at result[pos], then advance the winning pointer inward (l++ or r--) and decrement pos. You always fill the result from right to left, largest square first.

Hint 3Why fill from right? Because we're finding the largest remaining square at each step.▼

At each iteration we extract the maximum remaining square — but the output must be sorted ascending. Filling from the right means the largest value goes to the last position, second-largest to second-to-last, and so on, naturally building a sorted array without any extra sorting step. The key insight: at any moment, the unfilled result[pos] is exactly the right slot for the current maximum.

🌐 Real-World Analogy

Placing Tiles by Size

Imagine you have tiles of various sizes lined up in a row, where the smallest tiles are in the middle and the largest are at both ends (the far left and far right). You want to stack them in a new row from smallest to largest. Your strategy: always compare the two outermost tiles, pick the bigger one, place it at the last open slot in your new row, then move inward. This builds the sorted result naturally — largest to smallest from right to left — without needing a separate sorting pass.

Brute Force Approach — Square and Sort

O(n log n) Time

🧮

Square Each Element, Then Sort

Time O(n log n)Space O(n) or O(1)

The simplest approach is to first map every element in the array to its square. Then, use a built-in sorting algorithm to sort the new array.

1Iterate through the array and replace each nums[i] with nums[i] * nums[i].
2Sort the resulting array.
3Return the sorted array.

Why it's not optimal: Sorting takes O(n log n) time. Since the original array is already sorted, we are ignoring a very important constraint we could use to optimize our solution to O(n) time.

def sortedSquares(nums):
    for i in range(len(nums)):
        nums[i] *= nums[i]
    nums.sort()
    return nums

Approach — Two Pointers, Fill Right-to-Left

O(n) Time · O(n) Space

📐

Compare Ends, Place Largest Square at pos, Move Inward

Time O(n)Space O(n)

The input is sorted, so the largest squares are always at the ends. Use two pointers l (left, blue) and r (right, orange). At each step compare abs(nums[l]) vs abs(nums[r]), place the larger square at result[pos], advance the winning pointer inward, and decrement pos.

1Initialize result = [0]*n, l=0, r=n-1, pos=n-1.
2While l <= r: compare abs(nums[l]) vs abs(nums[r]).
3If abs(l) > abs(r): place nums[l]² at result[pos], l++.
4Else: place nums[r]² at result[pos], r--.
5Decrement pos after each placement. Return result.

Status

READY—

Press ▶ or step forward to begin.

l—

r—

pos—

nums[l]²—

nums[r]²—

✓

—

nums (sorted)

Space Play/Pause·←→ Step·R Reset

Executing Code

def sortedSquares(nums):

    n = len(nums)

    result = [0] * n

    l, r = 0, n - 1

    pos = n - 1

    while l <= r:

        if abs(nums[l]) > abs(nums[r]):

            result[pos] = nums[l] ** 2

            l += 1

        else:

            result[pos] = nums[r] ** 2

            r -= 1

        pos -= 1

    return result

Discussion

…

Loading comments…

LeetMotion