Sorted Squares of Readings
EasyTwo Pointers
Problem
A calibration tool records signed deviations nums, sorted in non-decreasing order. For an error report it needs the square of every deviation, also sorted in non-decreasing order.
Return that list in O(n) time.
Example 1
- Input:
- nums = [-6, -2, 0, 3, 5]
- Output:
- [0, 4, 9, 25, 36]
The squares are [36, 4, 0, 9, 25]; sorted they become [0, 4, 9, 25, 36].
Example 2
- Input:
- nums = [-3, -1]
- Output:
- [1, 9]
Constraints
- 1 ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
- nums is sorted in non-decreasing order
Hint
Show the first hint
Where in the input can the largest square come from?
Walkthrough
How to approach it
01Clarify before coding
- Can all values be negative, or all positive? Yes, both happen.
- Is a new array allowed? Yes, return a new list.
- Can squares overflow? No: 10^4 squared is 10^8, which fits in a 32-bit integer.
02Brute force
Square every element, then sort the squares.
Cost: O(n log n) time: correct, but ignores that the input is already sorted.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.