Squares of a Sorted Array
Easy · Arrays & Hashing · Array · Two Pointers · Sorting
Problem
You are given an integer array nums sorted in non-decreasing order. It may contain negative numbers.
Return a new array holding the square of every element, also sorted in non-decreasing order.
Squaring and then sorting costs O(n log n). The largest squares sit at the two ends of the array, so a two-pointer pass that fills the result from the back does it in O(n).
Examples
Input: nums = [-5,-2,0,3] Output: [0,4,9,25]
The squares are 25, 4, 0 and 9, which sort to [0,4,9,25].
Input: nums = [-3,-3,1] Output: [1,9,9]
Both -3 values square to 9.
Input: nums = [2,4] Output: [4,16]
Every value is non-negative, so the squares are already in order.
Constraints
- 1 <= len(nums) <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order
Approaches
- Baseline: square everything, then sort — time O(n log n), space O(n)
Follow-up
Could you do it without the absolute values, by first finding where the negatives end (a binary search for the first value >= 0) and then merging outward from there, smallest squares first? Both versions are O(n); which one is easier to get right?
Related problems
Start free on Cariara · Coding problems · System design studio
