#977 Squares of a Sorted Array
the problem
In plain words
nums is sorted in non-decreasing order and may contain negative numbers. Return a new array holding the square of every number, also sorted in non-decreasing order.
in nums = [-4,-1,0,3,10]
out [0,1,9,16,100]
Squares are [16,1,0,9,100]; sorted: [0,1,9,16,100].
in nums = [-7,-3,2,3,11]
out [4,9,9,49,121]
- 1 ≤ n ≤ 10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- Sorted non-decreasing
- Follow-up: O(n)
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo pointers (opposite ends)
Squaring flips the order of the negatives, but the biggest square is always at one of the two ends. So build the answer from the back, taking the bigger end each time.
solutions
From brute force to optimal
Square every number, then let Arrays.sort fix the order.
- result[i] = nums[i] * nums[i].
- Arrays.sort(result).
Sorting n squares ignores that the input was already sorted.
The sort's recursion stack; the output array itself doesn't count.
class Solution { public int[] sortedSquares(int[] nums) { int[] result = new int[nums.length]; for (int i = 0; i < nums.length; i++) result[i] = nums[i] * nums[i]; Arrays.sort(result); // negatives made the squares unsorted return result; }}The largest absolute value is at one of the ends. Compare the two ends' squares and place the larger at the back.
- left = 0, right = n − 1.
- For k from n − 1 down to 0: compare nums[left]² with nums[right]².
- Write the larger at result[k] and move that pointer inward.
Each step fills one slot of the result.
Only the output array and two indices.
class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; int left = 0, right = n - 1; for (int k = n - 1; k >= 0; k--) { // biggest square first, written at the back int l = nums[left] * nums[left], r = nums[right] * nums[right]; if (l > r) { // the most negative number wins result[k] = l; left++; } else { result[k] = r; right--; } } return result; }}in the room
How to say it in the interview
talk track
- Point out that after squaring there are two sorted runs: the negatives (reversed) and the rest.
- Say why the ends hold the largest absolute values — that's what lets you fill the result biggest-first.
traps
- Trying to fill from the front: the smallest square sits somewhere in the middle, so you don't know where to start.
- Comparing
nums[left]withnums[right]instead of their squares: −7 vs 2 picks the wrong side.
what they ask next
Follow-ups
Sort Transformed Array (LC 360): apply f(x) = ax² + bx + c to a sorted array?
Same ends-first idea: for a > 0 the biggest values are at the ends (fill from the back); for a < 0 the smallest are (fill from the front).
before you submit
Edge cases to test
- All non-negative: the squares are already in order.
- All negative: the order fully reverses.
- Mirrored values [-2, -2, 2, 2] → [4, 4, 4, 4].
- |nums[i]| ≤ 10⁴, so a square is at most 10⁸ and fits in an
int.
practise next
Similar problems
- #88Merge Sorted ArrayEasyin Two Pointers
- #167Two Sum II - Input Array Is SortedMediumin Two Pointers
- #11Container With Most WaterMediumin Two Pointers