Squares of a Sorted Array (LC 977)

Pattern: Two Pointers
Difficulty: Easy
Key Concept: In a sorted array, the largest squares come from the ends (most negative or most positive); merge into a result array from right to left.

Problem Statement

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.

Input: nums — integers sorted ascending (may contain negatives).
Output: A new array (or filled result) where each element is nums[i] * nums[i], sorted ascending.

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

---

1. Algorithm & Pseudocode

Brute force (square + sort)

1. Create array ans of length n.
2. For i from 0 to n-1:
     ans[i] = nums[i] * nums[i]
3. Sort ans (e.g. Arrays.sort(ans)).
4. Return ans.

Optimal (two pointers from ends, fill from the back)

1. n = length(nums), create result[n].
2. left = 0, right = n - 1, pos = n - 1.
3. While left <= right:
     if |nums[left]| > |nums[right]|:
         result[pos] = nums[left] * nums[left]
         left++
     else:
         result[pos] = nums[right] * nums[right]
         right--
     pos--
4. Return result.

Why from the back?
The biggest square should go at the last index of result; then we fill inward with the next largest.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why not just square and sort?
It works and is easy, but sorting costs O(n log n). The input is already sorted; that structure lets us produce sorted squares in O(n).

Why compare absolute values at the ends?
Negative numbers square to positive values. The smallest value (large negative) might have a larger square than something near the middle. The maximum absolute value in a sorted array always lives at one of the two ends (leftmost negative or rightmost positive). So the largest square is always at left or right.

Filling result from index n-1 down to 0
We repeatedly pick the side with the larger |value|, square it, place it at pos, then move that pointer. What remains is a smaller subproblem on the same two-ended structure.

Math.abs for readability
Comparing |a| and |b| avoids tricky sign logic when squaring.

---

3. The Dry Run

Sample: nums = [-4, -1, 0, 3, 10]
n = 5, indices 0..4.

Optimal (standard loop: if |nums[left]| > |nums[right]| take left, else take right; write at pos, then pos--):

Step	left	right	pos (write here)	Comparison	Chosen	Value written	left / right after
1	0	4	4	|-4| vs |10|	right	100	right → 3
2	0	3	3	|-4| vs |3|	left	16	left → 1
3	1	3	2	|-1| vs |3|	right	9	right → 2
4	1	2	1	|-1| vs |0|	left	1	left → 2
5	2	2	0	|0| vs |0| (tie → else)	right	0	right → 1

After step 5: left = 2, right = 1, so left <= right is false — loop ends.

result after each write:

After step	result
1	[_, _, _, _, 100]
2	[_, _, _, 16, 100]
3	[_, _, 9, 16, 100]
4	[_, 1, 9, 16, 100]
5	[0, 1, 9, 16, 100]

Final: [0, 1, 9, 16, 100] (sorted squares).

Note: When left == right, the else branch still runs; both sides refer to the same index, so the square is correct.

---

4. Java Solution

Brute Force

Idea: Square every element, then sort.

• Time: O(n log n) dominated by sort
• Space: O(1) extra if sorting in place on ans (excluding output array), or O(n) for the result array depending on interpretation

import java.util.Arrays;

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

Optimal

Idea: Two pointers; place largest squares from the end of result.

• Time: O(n) — one pass
• Space: O(n) for result (output), O(1) extra besides output

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

---

5. The “Java vs. Others” Edge

• Math.abs(int) returns a non-negative int for int arguments. In C++, <cstdlib> provides abs for integers; include the right header and watch types (long vs int).
• Arrays.sort(int[]) uses a tuned sort (historically dual-pivot Quicksort for primitive arrays). Average time is O(n log n); worst case for primitive int[] was O(n²) in older JDKs; later releases reduced pathological cases (e.g. Java 14+ changes for counting/patterns on mostly duplicate data). For interviews, still say O(n log n) for the sort step unless the interviewer wants JVM trivia.
• The two-pointer solution avoids sort entirely and is O(n) time — the usual “expected” optimal answer.
• Contrast with Python: sorted([x*x for x in nums]) is concise; Java’s explicit loops match how you’d explain the algorithm on a whiteboard.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n log n)	O(n) for output	Arrays.sort on squares
Optimal	O(n)	O(n) for output, O(1) extra	Two pointers from ends; no sort