Square Of Sorted Array
Description
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Explanation: Squares are [16, 1, 0, 9, 100]. After sorting: [0, 1, 9, 16, 100].
Example 2:
Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Explanation: Squares are [49, 9, 4, 9, 121]. After sorting: [4, 9, 9, 49, 121].
Example 3:
Input: nums = [1, 2, 3]
Output: [1, 4, 9]
Explanation: All positive, so squares are already sorted.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums is sorted in non-decreasing order
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Use two pointers at both ends of the array
- Approach
- Compare absolute values at both ends, place larger square at the end of result, move that pointer inward
- Complexity
- The largest squares are at the ends (negative or positive extremes)
Solutions
Show PY Solution
def solution(nums):
left = 0
right = len(nums) - 1
results = [0] * len(nums)
for i in range(len(nums), 0, -1):
a = nums[left]
b = nums[right]
aa = a * a
bb = b * b
if aa < bb:
results[i - 1] = bb
right -= 1
else:
results[i - 1] = aa
left += 1
return results