Two Pointers · 172Easy
Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number, also sorted in non-decreasing order.
Constraints
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in non-decreasing order.
Examples
sortedSquares([-4, -1, 0, 3, 10]) -> [0, 1, 9, 16, 100] sortedSquares([-7, -3, 2, 3, 11]) -> [4, 9, 9, 49, 121] sortedSquares([-5]) -> [25] // single element sortedSquares([-3, -2, -1]) -> [1, 4, 9] // all negative: squares reverse the order sortedSquares([1, 2, 3]) -> [1, 4, 9] // all non-negative: order is kept sortedSquares([-2, -1, 1, 2]) -> [1, 1, 4, 4] // mirrored values square to duplicates
Edge cases
- All negative: the squares come out in reverse order.
- All non-negative: already in order.
- FOLLOW-UP
- Squaring then sorting is O(n log n). Can you find an O(n) solution?
Show the target complexity (spoiler)
- Naive
- O(n log n) time — square everything, then sort.
- Target
- O(n) time, O(n) space for the output — pointers at both ends; place the larger square at the back of the result and move that pointer inward.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/02-two-pointers/172-squares-of-a-sorted-array.js ./practice c 172