Day 6 of 250: LeetCode 977 Squares of a Sorted Array | Two Pointers Explained Step by Step

Coming Off Yesterday: From Three Buckets to Two Ends

Yesterday on Day 5, we tackled LeetCode 75 Sort Colors using the Dutch National Flag algorithm. That problem taught us how to use three pointers to partition an array in place without any extra space. We maintained a low boundary, a high boundary, and a current scanner, and the whole thing ran in a single pass.

Today we are working with a different flavour of the same core instinct: using pointers at both ends of an array to extract information in the right order. But there is a twist. The input is already sorted, and we are transforming it. Squaring numbers sounds innocent until you realize that squaring a negative number makes it positive and potentially enormous, which completely destroys the sorted order we started with.

The problem on Day 6 is LeetCode 977: Squares of a Sorted Array. It is tagged Easy, but the efficient solution requires the same controlled two pointer thinking we practiced yesterday.

Let us get into it.

Problem Statement

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]

Example 2:

Input:  nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order

The Core Insight: The Largest Square Always Lives at One of the Two Ends

Here is the single observation that unlocks everything: when you square every element in a sorted array, the biggest results do not come from the middle. They come from either the far left (the most negative numbers) or the far right (the most positive numbers).

Think about it this way. If we have [-4, -1, 0, 3, 10], the absolute values at the two ends are |-4| = 4 and |10| = 10. After squaring, those are 16 and 100. The numbers closest to zero, like -1 and 0, produce the smallest squares. So the order of absolute values radiates outward from zero in both directions.

The naive approach most people would reach for is to square every element and then sort the result. That works. It gives you a correct answer. But it costs O(n log n) time because of the sort. The insight above tells us we can do better. We already know where the largest squares are: at the ends. If we always pick the larger of the two ends, place it in our result from right to left, and move the corresponding pointer inward, we process every element exactly once. That is O(n).

First Instincts vs. Correct Thinking

A beginner looking at this problem for the first time would likely do the following: square every element, then call .sort(). In JavaScript, that might look like this:

// Naive approach
var sortedSquares = function(nums) {
    return nums.map(x => x * x).sort((a, b) => a - b);
};

This is correct, and it is not wrong to start here. But an interviewer will almost always ask: "Can you do it in O(n)?" And that is where the naive approach hits a wall.

The mental shift required is to stop thinking about squaring first and then sorting. Instead, think about which elements will produce the largest squares. Those are always at the extremes. Once you accept that the max square at any moment is always at one of the two ends, you realize you can fill a result array from back to front, placing the largest value first and working toward the smallest. No sort needed. The array fills itself in order because we are always choosing the current maximum.

Understanding the Approach

We use three variables to drive the algorithm.

left starts at index 0 and points to the smallest (most negative or least positive) element in the remaining window. right starts at the last index and points to the largest element in the remaining window. current starts at the last index of the result array and tells us where to place the next value.

The rule for each step is this: compute the square of nums[left] and the square of nums[right]. Whichever is larger gets placed at res[current]. If nums[left] squared is larger, we move left one step to the right. If nums[right] squared is larger or if they are equal, we move right one step to the left. Either way, we decrement current by one. We repeat until left and right cross.

The reason we fill from the back is that we are always placing the current maximum. If we tried to fill from the front, we would need the current minimum, but we cannot be sure which end holds the minimum at any step without additional logic. Filling from the back is cleaner and provably correct.

Deep Dry Run: Every Step Explained

We will trace through nums = [-4, -1, 0, 3, 10] completely.

Initial state:

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

left    = 0
right   = 4
current = 4
res     = [ 0,  0,  0,  0,  0]

Iteration 1:

[-4]  -1   0   3  [10]
  ^                  ^
left               right

leftSquare  = (-4)^2 = 16
rightSquare = (10)^2 = 100

100 > 16, so rightSquare wins.
res[4] = 100, move right left by 1.

res     = [ 0,  0,  0,  0, 100]
left    = 0
right   = 3
current = 3

The largest square (100) is placed at the last slot, and the right pointer closes in.

Iteration 2:

[-4]  -1   0  [3]  10
  ^            ^
left          right

leftSquare  = (-4)^2 = 16
rightSquare = (3)^2  = 9

16 > 9, so leftSquare wins.
res[3] = 16, move left right by 1.

res     = [ 0,  0,  0, 16, 100]
left    = 1
right   = 3
current = 2

The left end had the bigger square this time. -4 squared beats 3 squared, so it goes into position 3.

Iteration 3:

-4  [-1]  0  [3]  10
      ^        ^
     left     right

leftSquare  = (-1)^2 = 1
rightSquare = (3)^2  = 9

9 > 1, so rightSquare wins.
res[2] = 9, move right left by 1.

res     = [ 0,  0,  9, 16, 100]
left    = 1
right   = 2
current = 1

3 squared is larger, so it fills position 2. The right pointer moves inward.

Iteration 4:

-4  [-1]  [0]  3  10
      ^    ^
    left  right

leftSquare  = (-1)^2 = 1
rightSquare = (0)^2  = 0

1 > 0, so leftSquare wins.
res[1] = 1, move left right by 1.

res     = [ 0,  1,  9, 16, 100]
left    = 2
right   = 2
current = 0

-1 squared is larger than 0 squared. Position 1 is filled with 1.

Iteration 5:

-4  -1  [0]  3  10
          ^
       left/right (same index)

leftSquare  = (0)^2 = 0
rightSquare = (0)^2 = 0

Equal, so the else branch runs (rightSquare is placed).
res[0] = 0, move right left by 1.

res     = [ 0,  1,  9, 16, 100]
left    = 2
right   = 1
current = -1

left > right now, so the loop ends.

Final output: [0, 1, 9, 16, 100]

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

The right end starts with 11^2 = 121, the left end has (-7)^2 = 49. Right wins: res[4] = 121. Then (-7)^2 = 49 vs 3^2 = 9. Left wins: res[3] = 49. Then (-3)^2 = 9 vs 3^2 = 9. Equal, right branch runs: res[2] = 9, right moves. Then (-3)^2 = 9 vs 2^2 = 4. Left wins: res[1] = 9. Finally 2^2 = 4 fills res[0] = 4.

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

What Made It Work: The Deeper Why

1. The maximum square is always at one of the two ends. This is provable because the array is sorted. The largest absolute values are necessarily at the leftmost (most negative) and rightmost (most positive) positions. Every element between them has a smaller or equal absolute value, and therefore a smaller or equal square. So at every step, the current max lives at one of the two boundary positions.

2. Filling from back to front guarantees sorted order without any re-sorting. We always place the current maximum at the current rightmost unfilled slot. Because we are always placing the largest remaining value, the result array builds in descending order of squares from right to left, which means ascending order from left to right when read normally. The invariant holds at every step, not just at the end.

3. No element is ever revisited or skipped. Each iteration of the loop moves either left one step right or right one step left. current always decrements. The loop runs exactly n times for an array of length n. This tight accounting is what gives us O(n) time.

4. The equal case is handled correctly by either branch. When leftSquare == rightSquare, it does not matter which one we place first. Both are the same value. The chosen convention (right branch runs) is arbitrary but consistent, and the other pointer will handle the remaining equal value in the next iteration.

The Code

var sortedSquares = function(nums) {
    let res = new Array(nums.length).fill(0);
    let left = 0, right = nums.length - 1, current = nums.length - 1;

    while (left <= right) {
        let leftSquare = nums[left] * nums[left];
        let rightSquare = nums[right] * nums[right];
        if (leftSquare > rightSquare) {
            res[current] = leftSquare;
            left++;
        } else {
            res[current] = rightSquare;
            right--;
        }
        current--;
    }
    return res;
};

We begin by creating res, a new array of the same length as nums, pre-filled with zeros. This is our output buffer. We declare left at the start, right at the end, and current also at the end since we fill the result from back to front.

The while (left <= right) condition ensures we process every element exactly once, including the case where both pointers land on the same index. Inside the loop, we compute leftSquare and rightSquare fresh on each iteration using multiplication rather than Math.pow for speed.

The if (leftSquare > rightSquare) branch handles the case where the left end has the bigger square. We place it at res[current] and move left rightward to shrink the window. The else branch handles the case where the right end wins or they are equal. We place rightSquare and move right leftward. In both branches, current-- advances our write position one step toward the front.

When the loop exits, res holds all squares in non-decreasing order, and we return it.

Complexity Analysis

Common Mistakes

Mistake 1: Forgetting the condition covers equal pointers.

A common error is writing while (left < right) instead of while (left <= right). This skips the element at the center index when the array has an odd length, leaving one square out of the result.

javascript

// Wrong
while (left < right) { ... }

// Correct
while (left <= right) { ... }

When left == right, both pointers are on the same element. It still needs to be squared and placed.

Mistake 2: Filling the result array from left to right.

If you fill from res[0] forward, you would need the current minimum, not the current maximum. But you cannot reliably determine which end holds the minimum without additional comparisons. Filling from the back exploits the fact that the maximum is always identifiable, which is the insight the whole algorithm is built on.

Mistake 3: Using Math.pow(nums[left], 2) without understanding the cost.

This is not a correctness issue but worth noting. nums[left] * nums[left] is faster than Math.pow(nums[left], 2) in JavaScript because Math.pow involves floating point overhead and function call cost. In an interview, using multiplication signals that you are thinking about performance at a granular level.

Mistake 4: Forgetting to handle negative-only or positive-only arrays.

The algorithm works correctly for all-negative arrays like [-5, -3, -1] and all-positive arrays like [1, 2, 4]. Some beginners convince themselves they need special cases. They do not. The two pointer logic handles both without modification.

Mistake 5: Squaring once but comparing twice.

A subtle bug is computing leftSquare outside the loop and only recomputing it inside one branch. This leads to stale values being compared in subsequent iterations.

// Wrong
let leftSquare = nums[left] * nums[left]; // computed once, stale in next loop
while (left <= right) { ... }

// Correct: compute both inside the loop on every iteration
while (left <= right) {
    let leftSquare = nums[left] * nums[left];
    let rightSquare = nums[right] * nums[right];
    ...
}

Interview Tips

Step 1: Restate the constraint that unlocks everything. Say: "The key observation is that because the array is already sorted, the largest absolute values, and therefore the largest squares, are always at one of the two ends. That means I do not need to sort again."

Step 2: Explain the direction of fill before writing any code. Say: "I will use a result array and fill it from back to front. At each step, I compare the squares of the two end elements, place the larger one at the current position in the result, and move that pointer inward."

Step 3: Define all three variables and their roles clearly. Say: "left tracks the left boundary, right tracks the right boundary, and current is my write pointer in the result array. It starts at the last index."

Step 4: Walk through one or two iterations on a small example before writing code. Trace [-4, -1, 0, 3, 10] for two or three steps. This shows you are not just reciting a solution but actually understanding it.

Step 5: State time and space complexity before the interviewer asks. Say: "This runs in O(n) time since every element is touched exactly once. Space is O(n) for the result array, which is unavoidable since we need to return a new array."

Key Takeaways

Sorted input does not always stay sorted after transformation. Squaring a sorted array scrambles the order for negative numbers, which is the entire reason the naive approach needs a sort and why we need a smarter solution.

Filling a result array from back to front is a powerful trick. Whenever you can identify the current maximum more easily than the current minimum, filling backwards lets you exploit that knowledge without any extra bookkeeping.

Two pointers are about controlled decision making, not just movement. At each step, we make a precise comparison, take a precise action, and move exactly one pointer. That discipline is what keeps the algorithm correct and linear.

Recognizing which end holds the extreme value is the skill to build. Today it was about squares. Tomorrow it might be about products, distances, or sums. The habit of asking "where does the largest or smallest value live?" is what separates a brute force thinker from someone who finds linear solutions.

Closing

Day 6 is in the books. We took a sorted array, dealt with the curveball that squaring breaks order, and rebuilt sorted output in a single O(n) pass using two pointers and a back-to-front fill strategy.

On Day 7, we will step into another classic: a problem where the sorted structure of the input lets us do something far more efficient than you would expect at first glance. The two pointer instinct we are building now will carry directly into it.

If you found today's breakdown useful, drop a comment below. What clicked for you? What is still fuzzy? I read every comment and use them to make future posts better.

See you on Day 7. 🚀

This post is part of my 250 Days DSA Challenge, solving one problem every day with a focus on intuition, patterns, and interview ready thinking.