1. Squares of a Sorted Array (LeetCode)
Model answer
The task
Given an array sorted in nondecreasing order, return a new array containing the square of each value, also sorted in nondecreasing order.
Key idea
Squaring can make negative values large, so the largest square must come from one of the two ends of the input. Compare the absolute values at both ends and fill the result from right to left.
Approach
- Set pointers at the first and last elements.
- Allocate a result array of the same length.
- Compare the absolute values at the pointers.
- Place the larger square at the current result position, then move the corresponding pointer inward.
- Continue until every position has been filled.
class Solution:
def sortedSquares(self, nums: list[int]) -> list[int]:
left, right = 0, len(nums) - 1
result = [0] * len(nums)
write = len(nums) - 1
while left <= right:
if abs(nums[left]) > abs(nums[right]):
value = nums[left]
left += 1
else:
value = nums[right]
right -= 1
result[write] = value * value
write -= 1
return result
Complexity:
- Time: O(n), since each input element is processed once.
- Space: O(n), for the returned array.
Common follow-ups
- Can this be done without allocating a result array? Not while returning a separate sorted array in the general case; the output itself requires O(n) space.
- What if the input is not sorted? Sort it first, which takes O(n log n), then use the two-pointer method.
- How do duplicates affect the algorithm? They need no special handling; equal absolute values produce equal squares.