Squares of a Sorted Array
Asked at Meta, Uber
Problem
Given an integer array sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. The two-pointer approach achieves O(n) time without sorting.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Easy | View all Meta questions → |
| Uber | Easy | View all Uber questions → |
How to Think About It
Naive: square every element, then sort. O(n log n). The sorted property allows O(n).
Key insight: the largest squares come from the most negative numbers (left end) or the largest positive numbers (right end). Compare absolute values from both ends.
Use two pointers from both ends. Compare nums[left]^2 vs nums[right]^2. Place the larger one at the end of the result array and move that pointer inward.
Why it works: in a sorted array, the extremes have the largest absolute values. Squaring preserves the order of absolute values. By filling the result from right to left, you avoid sorting.
Visual walkthrough for [-4,-1,0,3,10]:
left=0(-4), right=4(10). 10^2=100 > (-4)^2=16. result[4]=100. right=3.
left=0(-4), right=3(3). (-4)^2=16 > 3^2=9. result[3]=16. left=1.
left=1(-1), right=3(3). 3^2=9 > (-1)^2=1. result[2]=9. right=2.
left=1(-1), right=2(0). (-1)^2=1 > 0^2=0. result[1]=1. left=2.
left=2, right=2. 0^2=0. result[0]=0.
Result: [0,1,9,16,100].
Edge cases: all negative, all positive, mixed, single element, zeros.
Optimal Approach
Step 1: Set left = 0, right = n-1. Create result array of size n.
Step 2: For position i from n-1 down to 0:
If |nums[left]| > |nums[right]|: result[i] = nums[left]^2, left++
Else: result[i] = nums[right]^2, right--
Step 3: Return result.
You fill the result from the largest position down to 0. Each step places the next largest square.
Time: O(n) — single pass. Space: O(n) for the result.
What Trips People Up in Real Interviews
Sorting after squaring. That's O(n log n). The two-pointer approach is O(n) and is the expected solution.
Comparing squared values instead of absolute values. Squaring can overflow for large negative numbers. Compare abs() values instead.
Filling the result from left to right. You must fill from right to left because the largest squares are at the extremes.
Not handling the case where both pointers meet. When left == right, place the last element and stop.
Using a priority queue or heap. While it works in O(n log n), the two-pointer approach is simpler and faster.
Solution Code
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
for i in range(n - 1, -1, -1):
if abs(nums[left]) > abs(nums[right]):
result[i] = nums[left] ** 2
left += 1
else:
result[i] = nums[right] ** 2
right -= 1
return resultFrequently Asked Questions
What is the Squares of a Sorted Array problem?
Given an integer array sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. The two-pointer approach achieves `O(n)` time without sorting.
How do you solve Squares of a Sorted Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Squares of a Sorted Array?
Squares of a Sorted Array is asked at Meta, Uber. It is a easy difficulty problem.
What are common mistakes on Squares of a Sorted Array?
- Sorting after squaring. That's `O(n log n)`. The two-pointer approach is `O(n)` and is the expected solution.
- Comparing squared values instead of absolute values. Squaring can overflow for large negative numbers. Compare `abs()` values instead.
- Filling the result from left to right. You must fill from right to left because the largest squares are at the extremes.
- Not handling the case where both pointers meet. When left == right, place the last element and stop.
- Using a `priority queue` or `heap`. While it works in `O(n log n)`, the two-pointer approach is simpler and faster.