LeetCode · #977

Squares of a Sorted Array Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #977

🏗️

Pattern

Two Pointers — compare absolutes from ends

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. The input may contain negative numbers, so squaring can change the relative order.

Example 1

 Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
// (-4)²=16, (-1)²=1, 0²=0, 3²=9, 10²=100 → sorted: [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  ↑ Key: already sorted — the largest squares are at the ENDS 

Section Two · Approach 1

Brute Force — Square & Sort O(n log n)

Square every element, then sort the result. Simple and correct, but doesn't exploit the fact that the input is already sorted.

Why we can do better

Problem: Sorting costs O(n log n). The input is already sorted — the largest squares must be at either end (largest negatives or largest positives). Two pointers from both ends can build the result in O(n) by always picking the larger square.

Java — Square + Sort

 import java.util.Arrays;
class Solution {
public int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++)
            nums[i] = nums[i] * nums[i];
Arrays.sort(nums);
return nums;
    }
}

Python — Square + Sort

 class Solution:
def sortedSquares(self, nums: list[int]) -> list[int]:
return sorted(x * x for x in nums)

Metric	Value
Time	O(n log n) — dominated by sort
Space	O(1) or O(n) depending on sort

Section Three · Approach 2

Two Pointers — O(n)

Since the input is sorted, the largest squared values are at the extremes — either the most negative (left end) or the most positive (right end). Use two pointers from both ends, compare absolute values, and fill the result array from right to left (largest to smallest).

💡 Mental model: Imagine two runners at opposite ends of a number line. Each holds their squared value like a price tag. A judge compares their tags — the bigger one gets placed at the back of the podium. That runner steps inward. The judge fills the podium back-to-front with decreasing squares.

Algorithm

Step 1: Create result array of size n. Set left = 0, right = n - 1, pos = n - 1.
Step 2: While left ≤ right: compare |nums[left]| with |nums[right]|.
Step 3: Place the larger square at result[pos--]. Advance the pointer whose value was used.
Step 4: Return result.

🎯 When to recognize this pattern:

When the input is sorted and the desired output depends on absolute values or values that "mirror" around zero — the extremes hold the largest magnitudes.
Filling the result from the outside-in (or back-to-front) lets you avoid re-sorting.
This specific pattern is unique to LC 977 but the general idea of "sorted input → two-pointer merge from ends" is widely applicable.

Section Four · Trace

Visual Walkthrough

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

Two Pointers — fill result from right to left

Notice:

We fill the result from the back (largest first).
The two pointers ensure we always pick the largest remaining square. Each element is visited exactly once — O(n).

Section Five · Implementation

Code — Java & Python

Java — Two Pointers from ends

 class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 0, right = n - 1, pos = n - 1;
while (left <= right) {
int lSq = nums[left] * nums[left];
int rSq = nums[right] * nums[right];
if (lSq > rSq) {
                result[pos--] = lSq;
                left++;
            } else {
                result[pos--] = rSq;
                right--;
            }
        }
return result;
    }
}

Python — Two Pointers from ends

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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Square + Sort	O(n log n)	O(1)*	Doesn't use sorted-input property. *In-place sort.
Two Pointers ← optimal	O(n)	O(n)	Linear scan; O(n) for the result array (required by output)

Space note:

The O(n) space is for the output array — required by the problem. No additional space beyond that.
If you count only auxiliary space, it's O(1).

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All non-negative	`[0, 1, 2, 3]`	Already sorted after squaring. Right pointer dominates.
All negative	`[-3, -2, -1]`	Squaring reverses the order. Left pointer dominates.
Single element	`[5]`	Result is [25]. One iteration, left == right.
Zeros	`[-2, 0, 0, 3]`	0² = 0 ends up at the front. Works naturally.
Same absolute values	`[-3, 3]`	Both square to 9. The `else` branch handles ties — either order is fine since values are equal.

⚠ Common Mistake: Filling the result array from left to right (smallest first) instead of right to left. The two pointers identify the largest remaining square — so you must fill from the back. Filling from the front would require knowing the smallest square, which needs a different pointer setup.

← Back to Two Pointers problems

LearningTree

LC 977 · Squares of a Sorted Array — Solution & Explanation | DSA Guide