Squares of a Sorted Array
- 1 min read
- LC-Medium
3 years ago
Solution
- Two Pointer approach
- Either start from outer bounds and converge towards the middle, or start from the middle and converge outwards
- Converging from the middle is annoying due to the edge cases and stuff, converging from the outside is much easier
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def sortedSquares(self, nums: List[int]) -> List[int]:
l, r = 0, len(nums) - 1
sorted_squares = [None] * len(nums)
idx = len(nums) - 1
while l <= r:
if abs(nums[l]) > abs(nums[r]):
sorted_squares[idx] = nums[l] ** 2
l += 1
else:
sorted_squares[idx] = nums[r] ** 2
r -= 1
idx -= 1
return sorted_squares