JuniorCodeCommonNot answered yet
Sorted squares of a sorted array in O(n)
Given an array of integers sorted in non-decreasing order (it may contain negatives), return a new array of the squares of each number, also sorted in non-decreasing order.
Requirements:
element at the front.
- O(n) time — do not square-then-sort (that is O(n log n)).
- Handle negative values: the largest square may come from the most negative
std::vector<int> sortedSquares(const std::vector<int>& nums) {
// your code here
}Write the implementation.
Use two pointers at both ends: the largest square is at one of the ends because the input is sorted. Compare abs(nums[left]) and abs(nums[right]), write the larger square into the output from the back, and move that pointer inward. One pass, O(n) time and O(n) space.
- ✗Squaring then sorting, losing the O(n) bound the two-pointer approach gives
- ✗Assuming the squares are already sorted because the input was — false when negatives are present
- ✗Filling the output front-to-back instead of back-to-front, so the larger squares land in the wrong slots
- →Where exactly does the largest square live before you start, and why?
- →How would the approach change if the input were not sorted at all?
Contents
Task
Given a non-decreasing array (negatives possible), return the squares of its elements in non-decreasing order in O(n).
Solution
std::vector<int> sortedSquares(const std::vector<int>& nums) {
int n = static_cast<int>(nums.size());
std::vector<int> result(n);
int left = 0, right = n - 1, pos = n - 1;
while (left <= right) {
int l = nums[left] * nums[left];
int r = nums[right] * nums[right];
if (l > r) { result[pos--] = l; ++left; } // larger square on the left
else { result[pos--] = r; --right; } // larger square on the right
}
return result;
}Key points
- The largest-magnitude element sits at one of the ends, so two pointers converge inward.
- The output is filled from the back with the current maximum square.
- One pass gives O(n); the "square then sort" variant is O(n log n).
Contents
