easyTwo PointersPure DSA~13 min
Sorted Squared Latencies
A monitoring job stores signed latency deltas (early or late) sorted ascending. To plot magnitude-squared deviations it needs the squares, still sorted ascending — without a full re-sort.
Problem
Given an array nums sorted in non-decreasing order (possibly containing negatives), return an array of the squares of each value, sorted in non-decreasing order.
Input
A sorted array nums of length n (1 ≤ n ≤ 10^5), values in [-10^4, 10^4].
Output
A sorted array of the squared values.
Constraints
- nums is sorted ascending
- 1 ≤ n ≤ 100,000
- Target O(n) without sorting the squares
Examples
Example 1
Input
nums = [-4, -1, 0, 3, 10]
Output
[0, 1, 9, 16, 100]
Squares are 16,1,0,9,100; merged from both ends they come out sorted.
Example 2
Input
nums = [-7, -3, 2, 3, 11]
Output
[4, 9, 9, 49, 121]
The largest squares live at the two ends of the sorted input.