Two Pointers — Squares of a Sorted Array
↗ LeetCode: Squares of a Sorted Array · Easy · pattern chapter →
Asked atAmazonGoogleMeta
Return squares of a sorted (possibly-negative) array, sorted.
Example 1 — nums=[-4,-1,0,3,10] → [0,1,9,16,100]Example 2 — nums=[-7,-3,2,3,11] → [4,9,9,49,121]
Constraints — 1 ≤ n ≤ 10⁴; sorted ascending. Brute square-then-sort is O(n log n) = 10⁵·17 ≈ 2·10⁶ ops at n=10⁵. Two-pointer from ends (largest square is at one edge) is O(n) = 10⁵ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Square then sort
O(n log n).
Approach 2 — Two pointers filling from back (canonical)
Insight. Largest square is at one of the two ends. Compare, place at k = n-1, decrement, repeat.
java
int[] sortedSquares(int[] nums) {
int n = nums.length, l = 0, r = n - 1, k = n - 1;
int[] out = new int[n];
while (l <= r) {
int a = nums[l] * nums[l], b = nums[r] * nums[r];
if (a > b) { out[k--] = a; l++; }
else { out[k--] = b; r--; }
}
return out;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n); Space O(n) for output.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Sort | O(n log n) | O(n) | baseline |
| Fill from back | O(n) | O(n) | canonical |
When to use which
- "Sorted array with monotone-transform" → fill-from-ends technique.
- In-place mutation → different — see Merge Sorted Array.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems