#977
Squares of a Sorted Array
Easy Opposite ends, fill from back
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given a sorted array that may contain negatives, return the squares of all elements in sorted order.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: square everything and return it sorted. Negatives make the squares unsorted.
Why this works: the biggest square is always at one of the two ends. Fill the answer from the back with the bigger end.
Example: [-4, -1, 0, 3, 10]
16 vs 100 → 100 at the back16 vs 9 → 161 vs 9 → 91 vs 0 → 1, then 0[0, 1, 9, 16, 100]
✦Hints open one at a time
The largest square is at one of the two ends.
Fill the result from the back with the larger of the two end squares.
↗Approach
Pointers at both ends. Compare absolute values, write the bigger square at the current back position of the result, and move that pointer inward.
</>Solution (Java)
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int l = 0, r = n - 1;
for (int k = n - 1; k >= 0; k--) {
if (Math.abs(nums[l]) > Math.abs(nums[r])) {
res[k] = nums[l] * nums[l];
l++;
} else {
res[k] = nums[r] * nums[r];
r--;
}
}
return res;
}
}!Common mistake
Squaring then sorting — O(n log n) and misses the two-pointer idea.
Complexity
- Time: O(n).
- Space: O(n) for the output.
