LeetCode 977: Squares of a Sorted Array
Difficulty: Easy | Pattern: Two Pointers | Language: C++
Problem Summary: Given a sorted integer array nums, return an array of the squares of each number sorted in non-decreasing order.
Example
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Brute Force Approach
Square every element and then sort the resulting array.
vector<int> ans;
for (int x : nums) {
ans.push_back(x * x);
}
sort(ans.begin(), ans.end());
| Metric |
Value |
| Time Complexity |
O(n log n) |
| Space Complexity |
O(n) |
How to Think About It
The largest square will always come from either the leftmost negative number or the rightmost positive number.
Compare the absolute values at both ends. Place the larger square at the end of the answer array and move the corresponding pointer inward.
Mental Model: The biggest square is hiding at one of the two ends.
Dry Run
| Left |
Right |
Chosen Square |
Answer Array |
| -4 |
10 |
100 |
[_, _, _, _, 100] |
| -4 |
3 |
16 |
[_, _, _, 16, 100] |
| -1 |
3 |
9 |
[_, _, 9, 16, 100] |
Optimized C++ Solution
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
int left = 0, right = n - 1;
for (int i = n - 1; i >= 0; --i) {
if (abs(nums[left]) > abs(nums[right])) {
ans[i] = nums[left] * nums[left];
left++;
} else {
ans[i] = nums[right] * nums[right];
right--;
}
}
return ans;
}
};
| Metric | Value |
|---|
| Time Complexity | O(n) |
| Extra Space | O(1) (excluding output array) |
Code Explanation
- Use two pointers: one at the beginning and one at the end.
- Compare
abs(nums[left]) and abs(nums[right]). - Place the larger square at position
i from the end of the answer array. - Move the pointer that produced the larger square.
Common Mistakes
Mistake 1: Filling the answer array from the beginning. Since the largest square is found first, fill the array from the end.
Mistake 2: Comparing raw values instead of absolute values.
Interview Follow-up
Q. Can we solve this without sorting?
Answer: Yes. The two-pointer approach avoids sorting entirely and runs in linear time.
Related Problems
- 26. Remove Duplicates from Sorted Array
- 27. Remove Element
- 88. Merge Sorted Array
Last Updated: July 22, 2026