Squares of a Sorted Array: Two Pointers from Both Ends

LeetCode Squares of a Sorted Array (problem 977) is one of those easy problems that reveals a beautiful pattern if you look past the brute force. You could square everything and sort, but there is a linear-time trick hiding in the input's sorted order. The key is realizing where the largest squares live.

The problem

You are given an integer array nums sorted in non-decreasing order. Return an array of the squares of each number, also sorted in non-decreasing order.

Example: nums = [-4, -1, 0, 3, 10] returns [0, 1, 9, 16, 100].

The catch is that negative numbers exist. Squaring [-4, -1, 0, 3, 10] gives [16, 1, 0, 9, 100], which is not sorted. You need to produce the sorted result efficiently.

The brute force: square and sort

The most obvious approach is to square every element and then sort the result. That works perfectly fine.

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

This runs in O(n log n) because of the sort. But you can do better. The input is already sorted, and that structure gives you enough information to produce the output in O(n) time.

The key insight: largest squares are at the ends

This is exactly the structure you need for a two-pointer merge. Place one pointer at the left end and one at the right end. Compare the absolute values (or equivalently, compare the squares). Whichever is larger goes into the result array at the current position, and you fill the result from right to left.

Step-by-step walkthrough

Let's trace through nums = [-4, -1, 0, 3, 10]. The left pointer (L) starts at index 0 and the right pointer (R) starts at index 4. We fill the result array from the last position backward.

Each step compares the absolute values at L and R, places the larger square into the next open position from the right, and moves the corresponding pointer inward. When the pointers meet, every position has been filled and the result is fully sorted.

The code

def sorted_squares(nums):
    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 loop runs while left has not passed right. At each iteration, you compare the absolute values at both ends. The larger one gets squared and placed at pos, then you shrink the window from that side. The pos pointer moves left on every iteration, so each slot gets filled exactly once.

When abs(nums[left]) equals abs(nums[right]), the else branch fires, placing the right element first. Either choice is correct since both squares are equal.

Complexity analysis

The two-pointer approach visits each element exactly once, giving O(n) time. Both approaches use O(n) space for the output array. If you do not count the output, the two-pointer solution uses O(1) extra space since you only need three integer variables.

The building blocks

Two pointers from opposite ends

The core pattern here is placing two pointers at the boundaries of a sorted array and walking them inward. You compare values at both ends to decide which pointer moves. This same structure shows up in problems like Two Sum II, Container With Most Water, and 3Sum. Whenever a sorted array needs to be scanned from both sides, reach for this pattern.

Merging two sorted sequences into one

Filling the result array from one end while pulling from two sources is the same merge operation you see in merge sort. Here, the two "sorted sequences" are the left half (sorted by descending absolute value from left to right) and the right half (sorted by ascending absolute value from left to right). You merge them by always picking the larger of the two candidates. The same idea appears in Merge Sorted Array (LeetCode 88), where you fill from the back to avoid overwriting.

Edge cases

• All non-negative values. The array is already sorted by absolute value. The right pointer does all the work, and the result is just the squares in order.
• All negative values. The left pointer does all the work. Squares come out in reverse order of the input, which is correct since the most negative value has the largest square.
• Single element. The loop runs once, squares the only value, and returns it.
• Zeros in the array. Zeros square to zero and end up at the front of the result. No special handling needed.
• Duplicates with opposite signs. For example, [-3, 3] both square to 9. The algorithm places them consecutively, which is correct.

From understanding to recall

This problem is rated easy, and the two-pointer solution is only about ten lines. That simplicity is deceptive. The insight that the largest squares live at the ends, not the middle, is the kind of observation that feels obvious after you see it but hard to generate under pressure. If you have not practiced producing this solution from memory, you will likely default to the sort-based approach in an interview and miss the O(n) answer.

Spaced repetition helps you internalize the pattern. Write the solution from scratch today, then again in a few days, then a week later. After a few reps, the two-pointer setup and the right-to-left filling become automatic. You will not need to rederive the approach because it will already be part of your toolkit.

Related posts

• Merge Sorted Array - Two-pointer merge of sorted arrays, filling from the end
• Sort Colors - In-place array partitioning with multiple pointers
• Two Sum II - Two-pointer technique on a sorted array