K Smallest Squares from a Sorted Array
Uber● MediumFULLTIMEONSITE INTERVIEWProblem statement
Given an integer array sorted in nondecreasing order, return the k smallest squared values in nondecreasing order.
Use 64-bit arithmetic for every square. The intended solution locates the split between negative and nonnegative values with binary search and merges outward from that split without materializing and sorting all squared values.
Function
kSmallestSquares(nums: int[], k: int) → long[]Examples
Example 1
nums = [-7,-3,-1,4,8]k = 3return = [1,9,16]The three smallest squares come from -1, -3, and 4.
Example 2
nums = [-2,-2,0,3]k = 4return = [0,4,4,9]Duplicate input magnitudes produce duplicate squares.
Example 3
nums = [-1000000000,2]k = 1return = [4]The square of 2 is smaller; 64-bit arithmetic is required for the other value.
Constraints
0 <= nums.length <= 200000.0 <= k <= nums.length.-10^9 <= nums[i] <= 10^9.numsis sorted in nondecreasing order.