Given an integer array nums sorted in non-decreasing order, which may contain negative numbers, return a new array with the square of each number, also sorted in non-decreasing order.
Example 1
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
The squares are
[16,1,0,9,100], which sorted become [0,1,9,16,100].Example 2
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- `nums` is sorted in non-decreasing order
Hints
Frequently asked at: Meta, Amazon, Uber, Apple
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Squaring every number and sorting works in O(n log n). But the input is already sorted: large negative numbers on the left and large positive numbers on the right both give big squares, so the biggest square is always at one of the two ends. Compare the two ends, place the larger square at the last free slot of the result, and move that pointer inward. This fills the answer in O(n).
Algorithm
- Create
resof sizen, setl = 0,r = n - 1,pos = n - 1. - While
l <= r, compareabs(nums[l])andabs(nums[r]). - Write the larger square to
res[pos]and move that pointer inward. - Decrease
posand repeat, then returnres.
Time:
O(n)Space: O(n) for the outputInterview tip: Students often try to start from the smallest absolute value in the middle; filling from the back with the largest square is simpler and avoids searching for the split point.
class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n l, r = 0, n - 1 for pos in range(n - 1, -1, -1): # The largest remaining square sits at one of the two ends. if abs(nums[l]) > abs(nums[r]): res[pos] = nums[l] * nums[l] l += 1 else: res[pos] = nums[r] * nums[r] r -= 1 return resCtrl + Enter runs the examples