Loading…

easyArraysLC #977Frequently asked

Squares of a Sorted Array

Q: How do you solve Squares of a Sorted Array using the Square Then Sort (Brute Force) approach?

When to use it: State it as the obvious baseline that always works, then offer the O(n) merge as the follow-up answer they're fishing for. The bulletproof baseline: map each value to its square, then sort. It works on *any* integer array, sorted or not. **Why it's worth stating.** It's correct in three lines and demonstrates you can ship something immediately. It also sets up the contrast the interviewer wants: 'this ignores that the input is already sorted.' **Why it leaves performance on the table.** The input arrives sorted, and squaring corrupts that order only in a *structured* way (the U-shape). Re-sorting from scratch pretends we know nothing about the data — paying `log n` for information we already have. The follow-up line in the prompt is a direct invitation to do better. **Why we present it anyway.** Interviewers grade the progression. Stating the O(n log n) baseline and then *replacing* it with the O(n) merge shows you can both produce a working solution and refine it — exactly the signal an 'easy with a follow-up' is designed to elicit. Time complexity: O(n log n). Space complexity: O(n).

LCPractice

Two Pointers · 9 of 30 · 8 min

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

Follow-up: can you do it in O(n) time using a two-pointer technique, rather than the straightforward O(n log n) of squaring then sorting?

In plain English

Square every element and return them sorted. The twist: because negatives can have large magnitude, the squared values are NOT sorted just because the inputs were. But the structure is predictable — magnitudes decrease toward the center and increase outward — which a two-pointer merge exploits for O(n).

Examples

Example 1

Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Note: Squares are [16, 1, 0, 9, 100]; sorted gives [0, 1, 9, 16, 100]. The largest, 100, came from the right end; the next, 16, from the left end.

Example 2

Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Note: Squares [49, 9, 4, 9, 121] sorted. Note the two 9s from -3 and 3.

Example 3

Input: nums = [-5, -3, -1]
Output: [1, 9, 25]
Note: All negative: magnitudes decrease left-to-right, so squares are descending and need reversing.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in non-decreasing order

Clarifying questions4First question: Is the input guaranteed sorted, and how?Explore questions

Q1.Is the input guaranteed sorted, and how?
Yes, non-decreasing. That's the precondition that makes the O(n) two-pointer merge possible; without it you must sort.
Q2.Can the array contain negatives?
Yes — that's the whole point. A large negative like -8 squares to 64 and can dominate small positives, which is why squared order differs from input order.
Q3.Should the output keep duplicates?
Yes. Equal-magnitude values like -3 and 3 both produce 9; both appear in the output.
Q4.Any overflow concerns?
Values are within ±10⁴, so squares fit comfortably in 32-bit int (max 10⁸). No overflow handling needed here.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The biggest squares live at the two ends (largest negative or largest positive), not the middle. Put a pointer at each end, compare absolute values, square the larger, and write it into the result from the back forward. O(n) time, O(1) extra space — beats the obvious square-then-sort O(n log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit the sorted-but-signed structure to merge in O(n) instead of defaulting to square-then-sort O(n log n). It's an 'easy' that rewards seeing the U-shape and the two-monotonic-runs insight.

Where candidates slip

Squaring and sorting (correct but suboptimal), or trying to fill the result front-to-back and getting tangled — the largest values appear at the ends, so back-to-front is the natural fill order.

How to stand out

Say 'after squaring, magnitudes form two sorted runs from the center outward; I'll merge them from the ends into the result back-to-front, O(n) time, O(1) extra space.' Then mention this is exactly mergesort's merge.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Square Then Sort (Brute Force)	`O(n log n)`	`O(n)`	State it as the obvious baseline that always works, then offer the O(n) merge as the follow-up answer they're fishing for.	Read
2	Two Pointers Filling Back-to-Front (Optimal)Optimal	`O(n)`	`O(1)`	The follow-up answer they want. Lead with 'the largest square is always at one of the two ends'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSorted array with negativesabs(nums[lo]) vs abs(nums[hi])?left biggerright biggerExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Square Then Sort (Brute Force)

TimeO(n log n)SpaceO(n)

State it as the obvious baseline that always works, then offer the O(n) merge as the follow-up answer they're fishing for.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignore the sorted property for a second — what definitely produces the right answer regardless of input order?

2Hint 2Explore hint

Square every element, then sort the resulting array.

3Hint 3Explore hint

Correct and short, but the sort costs O(n log n) and ignores that the input was already sorted. The follow-up explicitly asks for better.

A · Core idea

The bulletproof baseline: map each value to its square, then sort. It works on any integer array, sorted or not.

Why it's worth stating. It's correct in three lines and demonstrates you can ship something immediately. It also sets up the contrast the interviewer wants: 'this ignores that the input is already sorted.'

Why it leaves performance on the table. The input arrives sorted, and squaring corrupts that order only in a structured way (the U-shape). Re-sorting from scratch pretends we know nothing about the data — paying log n for information we already have. The follow-up line in the prompt is a direct invitation to do better.

Why we present it anyway. Interviewers grade the progression. Stating the O(n log n) baseline and then replacing it with the O(n) merge shows you can both produce a working solution and refine it — exactly the signal an 'easy with a follow-up' is designed to elicit.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

square

[-4,-1,0,3,10] → [16,1,0,9,100]

Stateunsorted squares

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

C · Code with teaching comments

Reference implementation previewpublic int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = nums[i] * nums[i];Explore the full code

solution.javaJava

Square Then Sort (Brute Force) — reference

2 teaching notes

1
public int[] sortedSquares(int[] nums) {
2
    int n = nums.length;
3
    int[] res = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        // Square each value; squares of negatives become large positives, breaking
6
        // sorted order.
7
        res[i] = nums[i] * nums[i];
8
    }
9
    // The O(n log n) step — correct but ignores the input was already sorted.
10
    Arrays.sort(res);
11
    return res;
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

When a problem hands you a sorted input and then asks a follow-up for sub-n log n, that's a near-certain hint that a linear merge or two-pointer pass exists — the sort is the thing to eliminate.

ComplexityO(n log n) time, O(n) space — Squaring is O(n); sorting the squares dominates at O(n log n). Output (and the sort) use O(n) space.

E · Edge cases and pitfalls3Stopping here when the follow-up explicitly asks for O(n).Explore edge cases

Pitfalls

Stopping here when the follow-up explicitly asks for O(n).
Sorting the original values instead of the squares.
Forgetting that negatives can outrank positives after squaring.

03.2

Approach 2 of 2 · Optimal

Two Pointers Filling Back-to-Front (Optimal)

TimeO(n)SpaceO(1)

The follow-up answer they want. Lead with 'the largest square is always at one of the two ends'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

After squaring, where does the single largest value live — the middle, or an end? Try it on [-4, -1, 0, 3, 10].

2Hint 2Explore hint

It's always at one of the two ends (largest negative or largest positive). Compare absolute values at lo and hi to find it.

3Hint 3Explore hint

Allocate the result and fill it from the LAST index backward: write the bigger square, move that pointer inward, decrement the write position.

A · Core idea

Set lo = 0, hi = n − 1, and a write position pos = n − 1. At each step compare |nums[lo]| with |nums[hi]|; the larger magnitude squares to the larger value, so write that square at res[pos], move the chosen pointer inward, and decrement pos. Continue until every slot is filled.

Why the largest square is always at an end. The array is sorted, so the most negative value sits at the far left and the most positive at the far right. Squaring maps both to large positives. Any element between them has a magnitude no larger than at least one boundary value (magnitudes decrease as you move toward zero and increase away from it). So the maximum square is guaranteed to be at lo or hi — never strictly inside. That's the structural fact that makes a two-pointer merge correct.

Why we fill back-to-front. Because we can cheaply identify the current largest remaining square (it's at one end), it's natural to place values from largest to smallest — i.e., from the last index of the result toward index 0. Trying to fill front-to-front would require us to find the current smallest square, which can be at either end too, but back-to-front pairs perfectly with the 'max is at an end' fact and keeps the logic clean.

Why compare absolute values, not raw values. A raw comparison would say -4 < 3, but (-4)² = 16 > 9 = 3². The square depends only on magnitude, so the decision 'which end holds the bigger square' is exactly 'which end has the bigger absolute value'. Comparing raw signed values here is the classic bug.

Why this is just mergesort's merge. Read the array from the center outward in both directions and you get two already-sorted sequences of magnitudes (the left run descending toward zero, the right run ascending). Squaring preserves the order within each run. Merging two sorted runs is linear — and that's precisely what these two pointers do, except we emit the largest element each step and write it at the back.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

lo=0, hi=4 → pos=4

|−4|=4 < |10|=10 → write 100 at index 4

lo ↓

-4

[0]

-1

[1]

[2]

[3]

hi ↓

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Two Pointers Filling Back-to-Front (Optimal) — optimal

4 teaching notes

1
public int[] sortedSquares(int[] nums) {
2
    int n = nums.length;
3
    int[] res = new int[n];
4
    // Pointers at the two ends — where the largest squares always live.
5
    int lo = 0, hi = n - 1;
6
    // Fill the result back-to-front: largest square goes in the last slot first.
7
    for (int pos = n - 1; pos >= 0; pos--) {
8
        int left = nums[lo] * nums[lo];
9
        int right = nums[hi] * nums[hi];
10
        // Compare squared magnitudes; the bigger one is the next-largest remaining
11
        // value.
12
        if (left > right) {
13
            res[pos] = left;
14
            lo++;
15
        } else {
16
            res[pos] = right;
17
            hi--;
18
        }
19
    }
20
    return res;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Reframe the input as two monotonic runs of magnitudes meeting at the value closest to zero. Squaring keeps each run sorted, so the problem is a single merge of two sorted lists — O(n). The 'compare absolute values, write the bigger one at the back' move is the merge step; recognising sorted-runs-after-a-transform is the transferable skill.

ComplexityO(n) time, O(1) space — Each element is consumed exactly once as lo rises or hi falls, and each produces one write → O(n) time. Apart from the required output array, only two indices → O(1) extra space.

E · Edge cases and pitfalls8nums = [5] — Single element: one iteration writes 25 → [25].Explore edge cases

Edge cases handled

nums = [5]Single element: one iteration writes 25 → [25].
nums = [-5, -3, -1]All negative: left magnitudes are largest, so lo keeps winning → [1, 9, 25].
nums = [1, 2, 3]All non-negative: hi keeps winning → [1, 4, 9]; order already preserved.
nums = [-3, 3]Equal magnitudes: tie goes to the else (right) branch first → both 9s placed → [9, 9].

Pitfalls

Comparing raw values (nums[lo] vs nums[hi]) instead of absolute values/squares.
Filling the result front-to-back — the largest values belong at the back.
Off-by-one on pos or the lo/hi bounds, leaving a slot unwritten.
Appending to a list instead of indexing res[pos], producing reversed output.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; int lo = 0, hi = n - 1; for (int pos = n - 1; pos >= 0; pos--) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing signed values instead of magnitudes

−4 < 3 by sign, but (−4)² = 16 > 9 = 3². The next-largest square depends on absolute value, not sign.

Explore the code comparison

Don't write this

if (nums[lo] > nums[hi]) {
    res[pos] = nums[lo] * nums[lo];
    lo++;
}

Write this instead

int left = nums[lo] * nums[lo], right = nums[hi] * nums[hi];
if (left > right) {
    res[pos] = left;
    lo++;
}

Filling front-to-back

The two-pointer comparison cheaply identifies the current LARGEST remaining square, which must go in the last open slot — filling forward inverts the order.

Explore the code comparison

Don't write this

pos = 0
for ... :
    res[pos] = larger_square
    pos += 1

Write this instead

for pos in range(n - 1, -1, -1):
    res[pos] = larger_square

Defaulting to sort and ignoring the follow-up

Square-then-sort is correct but O(n log n); the prompt's follow-up explicitly asks for the O(n) two-pointer merge.

Explore the code comparison

Don't write this

return sorted(x * x for x in nums)  # ignores the O(n) follow-up

Write this instead

# two-pointer merge filling res back-to-front → O(n)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Opposite-end two pointers filling the result back-to-front

Code pattern to memorize

lo, hi = 0, n - 1
for pos in range(n - 1, -1, -1):   # fill from the END
    if abs(nums[lo]) > abs(nums[hi]):
        res[pos] = nums[lo] * nums[lo]; lo += 1
    else:
        res[pos] = nums[hi] * nums[hi]; hi -= 1

Rules to remember

1The largest square is at one of the two ends, so fill the result back-to-front (largest first).
2Compare absolute values (abs(nums[lo]) vs abs(nums[hi])) to decide which end to consume — squaring a negative can dominate.
3Use >=/else consistently so ties are handled deterministically; either end is fine on a tie.
4Allocate the result array up front and write by index, never append in the wrong order.
5Don't square-then-sort — it works but throws away the sorted input and costs an extra log n factor.

Use this pattern when

Input is **sorted**, but a transform (squaring) breaks that order in a predictable, U-shaped way
Extremes of the array hold the extremes of the transformed values
You want O(n) by merging two monotonic runs instead of re-sorting
Need a sorted output and can write it positionally

Choose another pattern when

Input is **unsorted** → just square and sort, O(n log n) is unavoidable
Transform preserves order (e.g. all non-negative) → trivial map, no two pointers needed
You need the squares in original order, not sorted → no merge trick applies
Values can overflow when squared and language has no big ints → mind the type

Interview takeaway

A sorted array of mixed signs squares into a U-shape: descending magnitudes on the left, ascending on the right. That's two sorted runs meeting in the middle — merge them from the outside in, filling the answer back-to-front, for O(n)/O(1). It's the merge step of mergesort in disguise.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo-pointer merge of two monotonic runs, filling the result back-to-front. Recognise it when a sorted input is transformed (squaring) into a predictable U-shape that's really two sorted sequences. Same engine as the merge step of mergesort and Merge Sorted Array.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Sorted Array
Same back-to-front fill trick — merge from the ends to avoid overwriting unprocessed values.
Two Sum II — Input Array Is Sorted
Opposite-end pointers on a sorted array, moving based on a comparison.
Sort Colors
Coming soon
Multi-pointer partitioning of a constrained array in O(n)/O(1).
Merge Two Sorted Lists
Coming soon
The merge step itself — two sorted sequences combined in linear time.

Same pattern

←

Two Sum II — Input Array Is Sorted

Continue · Next problem

Reverse Words in a String

easyArraysLC #977Frequently asked

Squares of a Sorted Array

LCPractice

Two Pointers · 9 of 30 · 8 min

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

Follow-up: can you do it in O(n) time using a two-pointer technique, rather than the straightforward O(n log n) of squaring then sorting?

In plain English

Examples

Example 1

Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Note: Squares are [16, 1, 0, 9, 100]; sorted gives [0, 1, 9, 16, 100]. The largest, 100, came from the right end; the next, 16, from the left end.

Example 2

Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Note: Squares [49, 9, 4, 9, 121] sorted. Note the two 9s from -3 and 3.

Example 3

Input: nums = [-5, -3, -1]
Output: [1, 9, 25]
Note: All negative: magnitudes decrease left-to-right, so squares are descending and need reversing.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in non-decreasing order

Clarifying questions4First question: Is the input guaranteed sorted, and how?Explore questions

Q1.Is the input guaranteed sorted, and how?
Yes, non-decreasing. That's the precondition that makes the O(n) two-pointer merge possible; without it you must sort.
Q2.Can the array contain negatives?
Yes — that's the whole point. A large negative like -8 squares to 64 and can dominate small positives, which is why squared order differs from input order.
Q3.Should the output keep duplicates?
Yes. Equal-magnitude values like -3 and 3 both produce 9; both appear in the output.
Q4.Any overflow concerns?
Values are within ±10⁴, so squares fit comfortably in 32-bit int (max 10⁸). No overflow handling needed here.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Squaring and sorting (correct but suboptimal), or trying to fill the result front-to-back and getting tangled — the largest values appear at the ends, so back-to-front is the natural fill order.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Square Then Sort (Brute Force)	`O(n log n)`	`O(n)`	State it as the obvious baseline that always works, then offer the O(n) merge as the follow-up answer they're fishing for.	Read
2	Two Pointers Filling Back-to-Front (Optimal)Optimal	`O(n)`	`O(1)`	The follow-up answer they want. Lead with 'the largest square is always at one of the two ends'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Square Then Sort (Brute Force)

TimeO(n log n)SpaceO(n)

State it as the obvious baseline that always works, then offer the O(n) merge as the follow-up answer they're fishing for.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignore the sorted property for a second — what definitely produces the right answer regardless of input order?

2Hint 2Explore hint

Square every element, then sort the resulting array.

3Hint 3Explore hint

Correct and short, but the sort costs O(n log n) and ignores that the input was already sorted. The follow-up explicitly asks for better.

A · Core idea

The bulletproof baseline: map each value to its square, then sort. It works on any integer array, sorted or not.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

square

[-4,-1,0,3,10] → [16,1,0,9,100]

Stateunsorted squares

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

C · Code with teaching comments

Reference implementation previewpublic int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = nums[i] * nums[i];Explore the full code

solution.javaJava

Square Then Sort (Brute Force) — reference

2 teaching notes

1
public int[] sortedSquares(int[] nums) {
2
    int n = nums.length;
3
    int[] res = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        // Square each value; squares of negatives become large positives, breaking
6
        // sorted order.
7
        res[i] = nums[i] * nums[i];
8
    }
9
    // The O(n log n) step — correct but ignores the input was already sorted.
10
    Arrays.sort(res);
11
    return res;
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

When a problem hands you a sorted input and then asks a follow-up for sub-n log n, that's a near-certain hint that a linear merge or two-pointer pass exists — the sort is the thing to eliminate.

ComplexityO(n log n) time, O(n) space — Squaring is O(n); sorting the squares dominates at O(n log n). Output (and the sort) use O(n) space.

E · Edge cases and pitfalls3Stopping here when the follow-up explicitly asks for O(n).Explore edge cases

Pitfalls

Stopping here when the follow-up explicitly asks for O(n).
Sorting the original values instead of the squares.
Forgetting that negatives can outrank positives after squaring.

03.2

Approach 2 of 2 · Optimal

Two Pointers Filling Back-to-Front (Optimal)

TimeO(n)SpaceO(1)

The follow-up answer they want. Lead with 'the largest square is always at one of the two ends'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

After squaring, where does the single largest value live — the middle, or an end? Try it on [-4, -1, 0, 3, 10].

2Hint 2Explore hint

It's always at one of the two ends (largest negative or largest positive). Compare absolute values at lo and hi to find it.

3Hint 3Explore hint

Allocate the result and fill it from the LAST index backward: write the bigger square, move that pointer inward, decrement the write position.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

lo=0, hi=4 → pos=4

|−4|=4 < |10|=10 → write 100 at index 4

lo ↓

-4

[0]

-1

[1]

[2]

[3]

hi ↓

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Two Pointers Filling Back-to-Front (Optimal) — optimal

4 teaching notes

1
public int[] sortedSquares(int[] nums) {
2
    int n = nums.length;
3
    int[] res = new int[n];
4
    // Pointers at the two ends — where the largest squares always live.
5
    int lo = 0, hi = n - 1;
6
    // Fill the result back-to-front: largest square goes in the last slot first.
7
    for (int pos = n - 1; pos >= 0; pos--) {
8
        int left = nums[lo] * nums[lo];
9
        int right = nums[hi] * nums[hi];
10
        // Compare squared magnitudes; the bigger one is the next-largest remaining
11
        // value.
12
        if (left > right) {
13
            res[pos] = left;
14
            lo++;
15
        } else {
16
            res[pos] = right;
17
            hi--;
18
        }
19
    }
20
    return res;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8nums = [5] — Single element: one iteration writes 25 → [25].Explore edge cases

Edge cases handled

nums = [5]Single element: one iteration writes 25 → [25].
nums = [-5, -3, -1]All negative: left magnitudes are largest, so lo keeps winning → [1, 9, 25].
nums = [1, 2, 3]All non-negative: hi keeps winning → [1, 4, 9]; order already preserved.
nums = [-3, 3]Equal magnitudes: tie goes to the else (right) branch first → both 9s placed → [9, 9].

Pitfalls

Comparing raw values (nums[lo] vs nums[hi]) instead of absolute values/squares.
Filling the result front-to-back — the largest values belong at the back.
Off-by-one on pos or the lo/hi bounds, leaving a slot unwritten.
Appending to a list instead of indexing res[pos], producing reversed output.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; int lo = 0, hi = n - 1; for (int pos = n - 1; pos >= 0; pos--) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing signed values instead of magnitudes

−4 < 3 by sign, but (−4)² = 16 > 9 = 3². The next-largest square depends on absolute value, not sign.

Explore the code comparison

Don't write this

if (nums[lo] > nums[hi]) {
    res[pos] = nums[lo] * nums[lo];
    lo++;
}

Write this instead

int left = nums[lo] * nums[lo], right = nums[hi] * nums[hi];
if (left > right) {
    res[pos] = left;
    lo++;
}

Filling front-to-back

The two-pointer comparison cheaply identifies the current LARGEST remaining square, which must go in the last open slot — filling forward inverts the order.

Explore the code comparison

Don't write this

pos = 0
for ... :
    res[pos] = larger_square
    pos += 1

Write this instead

for pos in range(n - 1, -1, -1):
    res[pos] = larger_square

Defaulting to sort and ignoring the follow-up

Square-then-sort is correct but O(n log n); the prompt's follow-up explicitly asks for the O(n) two-pointer merge.

Explore the code comparison

Don't write this

return sorted(x * x for x in nums)  # ignores the O(n) follow-up

Write this instead

# two-pointer merge filling res back-to-front → O(n)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Opposite-end two pointers filling the result back-to-front

Code pattern to memorize

lo, hi = 0, n - 1
for pos in range(n - 1, -1, -1):   # fill from the END
    if abs(nums[lo]) > abs(nums[hi]):
        res[pos] = nums[lo] * nums[lo]; lo += 1
    else:
        res[pos] = nums[hi] * nums[hi]; hi -= 1

Rules to remember

1The largest square is at one of the two ends, so fill the result back-to-front (largest first).
2Compare absolute values (abs(nums[lo]) vs abs(nums[hi])) to decide which end to consume — squaring a negative can dominate.
3Use >=/else consistently so ties are handled deterministically; either end is fine on a tie.
4Allocate the result array up front and write by index, never append in the wrong order.
5Don't square-then-sort — it works but throws away the sorted input and costs an extra log n factor.

Use this pattern when

Input is **sorted**, but a transform (squaring) breaks that order in a predictable, U-shaped way
Extremes of the array hold the extremes of the transformed values
You want O(n) by merging two monotonic runs instead of re-sorting
Need a sorted output and can write it positionally

Choose another pattern when

Input is **unsorted** → just square and sort, O(n log n) is unavoidable
Transform preserves order (e.g. all non-negative) → trivial map, no two pointers needed
You need the squares in original order, not sorted → no merge trick applies
Values can overflow when squared and language has no big ints → mind the type

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Sorted Array
Same back-to-front fill trick — merge from the ends to avoid overwriting unprocessed values.
Two Sum II — Input Array Is Sorted
Opposite-end pointers on a sorted array, moving based on a comparison.
Sort Colors
Coming soon
Multi-pointer partitioning of a constrained array in O(n)/O(1).
Merge Two Sorted Lists
Coming soon
The merge step itself — two sorted sequences combined in linear time.

Same pattern

←

Two Sum II — Input Array Is Sorted

Continue · Next problem

Reverse Words in a String