Mastering LeetCode Problem 0977 | Mohammad.H Mohammadi

Problem 0977: Squares of a Sorted Array

At first glance, LeetCode 977 – Squares of a Sorted Array looks trivial:

“Square all elements and sort the result.”

But if you’re serious about algorithmic thinking (and not just passing the problem), this question is a perfect playground for:

Understanding how to leverage existing sorting,
Practicing the two-pointer pattern,
Optimizing from O(n log n) down to O(n).

In this post, we’ll walk through:

Problem statement (clearly and briefly),
The naive approach and why it’s suboptimal,
The key insight behind the optimal solution,
A clean two-pointer implementation in Python,
A detailed step-by-step walkthrough,
Time & space complexity,
Common mistakes in interviews,
And how this pattern connects to other LeetCode problems (like 88, 283, 344).

1. Problem Statement

You are given a sorted integer array in non-decreasing order:

It may contain negative numbers,
Zero,
And positive numbers.

You must:

Square each number,
And return a new array of the squares,
Also sorted in non-decreasing order.

1.1. Example 1

Input:  nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]

1.1. Example 2

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

Constraints (simplified):

The array is already sorted.
Length is up to 10^4 (or larger depending on variant).
Values can be negative.

2. First Thought: Square Then Sort

The typical first idea:

Iterate through nums,
Replace each element with its square,
Sort the array.

Pseudo-code:

for i in range(len(nums)):
    nums[i] = nums[i] * nums[i]

nums.sort()
return nums

This solution:

Is simple and works,
Runs in:
- O(n) for squaring,
- O(n log n) for sorting.

Total time complexity: O(n log n).

For many real-world scenarios, this is good enough. But you’re on LeetCode / in an interview – this is where the fun starts:

The input array is already sorted. Ignoring that fact and sorting again is a waste of information.

Can we do better and achieve O(n) time?

Yes. And the key is to think about absolute values and two pointers.

3. Core Insight: Largest Square Comes from the Ends

Remember:

nums is sorted in non-decreasing order:
- Example: [-4, -1, 0, 3, 10].
Squaring changes the order because:
- Negative values become positive.
- Large negative numbers (e.g. -4) can have larger squares than small positive numbers (e.g. 3).

Key observation:

The largest square must come from either:
- The leftmost element (nums[0], most negative), or
- The rightmost element (nums[n-1], most positive), because those are the elements with the largest absolute values.

So instead of:

Squaring everything and sorting blindly,

we can:

Use two pointers (left and right),
Compare abs(nums[left]) and abs(nums[right]),
Take the larger square and place it at the end of the result array.

This leads directly to a two-pointer, O(n) solution.

4. Strategy: Two Pointers + Fill from the Back

We’ll build a result array result of the same size as nums:

Let left = 0, start of nums
Let right = n - 1, end of nums
Let k go from n - 1 down to 0 (fill result from right to left)

At each step:

Compute:
- square_left = nums[left] * nums[left]
- square_right = nums[right] * nums[right]
Compare:
- If square_left > square_right:
  - Set result[k] = square_left
  - Move left one step right (left += 1)
- Else:
  - Set result[k] = square_right
  - Move right one step left (right -= 1)
Decrease k and repeat.

When the loop ends, result is fully populated and sorted.

5. Python Implementation (Two-Pointer, O(n))

Here is a clean implementation that matches exactly this logic (and aligns with LeetCode’s expectations):

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        """
        Given a sorted integer array nums, returns an array of the squares
        of each number, also sorted in non-decreasing order.

        This uses a two-pointer approach:
        - One pointer at the beginning (left)
        - One pointer at the end (right)
        - Fill the result array from the largest square (end) backwards

        Time Complexity:  O(n)
        Space Complexity: O(1) extra (excluding the output array)
        """

        n = len(nums)
        result = [0] * n
        right, left = n - 1, 0

        # Fill result from the end (largest square) towards the beginning
        for k in range(n - 1, -1, -1):
            square_left = nums[left] * nums[left]
            square_right = nums[right] * nums[right]

            if square_left > square_right:
                result[k] = square_left
                left += 1
            else:
                result[k] = square_right
                right -= 1

        return result

This is the same algorithmic idea you implemented: optimal, simple, and clean.

6. Dry Run: Understanding the Flow

Let’s walk through the classic example step-by-step:

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

Initial:

n = 5
result = [0, 0, 0, 0, 0]
left = 0 → nums[left] = -4
right = 4 → nums[right] = 10

We will fill result from index k = 4 down to 0.

6.1. Iteration 1: k = 4

square_left = (-4)^2 = 16
square_right = 10^2 = 100
100 > 16 → use square_right

So:

result[4] = 100
Move right left: right = 3

Current state:

result = [0, 0, 0, 0, 100]
left   = 0  (nums[left] = -4)
right  = 3  (nums[right] = 3)

6.2. Iteration 2: k = 3

square_left = (-4)^2 = 16
square_right = 3^2 = 9
16 > 9 → use square_left

So:

result[3] = 16
Move left right: left = 1

Current state:

result = [0, 0, 0, 16, 100]
left   = 1  (nums[left] = -1)
right  = 3  (nums[right] = 3)

6.3. Iteration 3: k = 2

square_left = (-1)^2 = 1
square_right = 3^2 = 9
9 > 1 → use square_right

So:

result[2] = 9
Move right left: right = 2

Current state:

result = [0, 0, 9, 16, 100]
left   = 1  (nums[left] = -1)
right  = 2  (nums[right] = 0)

6.4. Iteration 4: k = 1

square_left = (-1)^2 = 1
square_right = 0^2 = 0
1 > 0 → use square_left

So:

result[1] = 1
Move left right: left = 2

Current state:

result = [0, 1, 9, 16, 100]
left   = 2  (nums[left] = 0)
right  = 2  (nums[right] = 0)

6.5. Iteration 5: k = 0

square_left = 0^2 = 0
square_right = 0^2 = 0
Equal → else-branch used (doesn’t matter which one we pick)

So:

result[0] = 0
Move right left: right = 1

Final:

result = [0, 1, 9, 16, 100]

We obtained the correct sorted squares in a single pass.

7. Time and Space Complexity

7.1. Time Complexity

We have a single loop from k = n-1 down to 0.
Each iteration does constant-time operations: a few multiplications, comparisons, and assignments.

Therefore:

$\text{Time Complexity} = O(n)$

This improves on the naive O(n \log n) solution that squares then sorts.

7.2. Space Complexity

We allocate a result array of size n (required by the problem).
Apart from that, we use only constant extra variables: left, right, k, square_left, square_right.

So:

$\text{Space Complexity} = O(1)$

This is optimal for this problem.

8. Edge Cases

8.1. All Non-Negative Numbers

nums = [0, 1, 2, 3]

Squaring keeps the array sorted: [0, 1, 4, 9].
Our algorithm still works:
- right pointer will always provide the larger square,
- We fill from right to left,
- Result remains sorted.

8.2. All Non-Positive Numbers

nums = [-7, -5, -3, -1]

Squaring yields [49, 25, 9, 1] (which is descending).
Our algorithm:
- Takes larger squares from the left side (most negative),
- Fills the result from the end,
- Effectively reverses those squares into non-decreasing order: [1, 9, 25, 49].

8.3. Mixed Negatives and Positives

nums = [-3, -1, 0, 2, 5]

The two-pointer logic correctly captures which side has the larger absolute value at each step.
No special cases needed; the algorithm is uniform.

8.4. Single Element

nums = [5]      # or [-5]

Only one value; its square is simply placed at result[0].

8.5. Empty Array

Even though LeetCode usually doesn’t give empty input for this problem:

nums = []

n = 0, result = [],
The loop doesn’t run,
result remains [].

The algorithm gracefully handles this case.

9. Common Interview Mistakes

Even with such a structured problem, candidates often fall into a few traps.

9.1. Ignoring the Input’s Sorted Property

Doing:

squares = [x * x for x in nums]
squares.sort()
return squares

This works, but:

Runs in O(n log n),
Fails to leverage the sorted nature of the input,
Is considered suboptimal in an interview context when a linear solution exists.

Interviewers want to see whether you notice and exploit problem-specific structure.

9.2. Mishandling Indices

Off-by-one errors are common:

Incorrect start or end indices in the loop,
Wrong range in range(...),
Mis-ordered updates to left and right.

The pattern for k in range(n - 1, -1, -1) and condition left <= right (implicitly via loop index) helps keep things clean.

9.3. Filling from the Front

Some candidates try to fill the result from the front:

This is harder because you don’t know where to place the smaller squares if you haven’t finished placing larger ones.
Filling from the back matches naturally with always choosing the current largest square.

9.4. Overcomplicating the Logic

Adding extra conditions, nested loops, or temporary arrays is a red flag:

This problem has a very clean solution,
Any unnecessary complexity suggests discomfort with two-pointer patterns.

10. How This Connects to Other Problems

This problem is not just about squares; it’s about patterns.

The same two-pointer-from-both-ends idea appears in:

LeetCode 88 – Merge Sorted Array
- Filling from the back while merging two sorted arrays.
LeetCode 283 – Move Zeroes
- Two pointers to compact and reorder elements in place.
LeetCode 344 – Reverse String
- Two pointers swapping from both ends towards the middle.
Palindrome checks, partitioning arrays, and more.

Mental pattern to remember:

“When you need to build a result array in sorted order and the largest elements are accessible from the ends, consider two pointers and fill from the back.”