977. Squares of a Sorted Array
easyGiven a sorted array of integers (possibly negative), return a new sorted array containing each element squared. Two-pointer classic that beats the naive sort by an order in clock time.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums is sorted in non-decreasing order.
Examples
Example 1
nums = [-4,-1,0,3,10][0,1,9,16,100]Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].
Example 2
nums = [-7,-3,2,3,11][4,9,9,49,121]Example 3
nums = [-5,-3,-2,-1][1,4,9,25]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
The naive square-then-sort is O(n log n). Can the input's sorted order buy you something cheaper?
Hint 2
The largest absolute value sits at one of the two ends of the input. Where does the next-largest sit?
Hint 3
Walk two pointers inward from both ends, writing squares into the result array from the back to the front.
Solution approach
Reveal approach
Maintain two pointers: left at index 0 and right at index n-1. Allocate a result array of the same length and fill it from right to left. At each step compare the absolute values at left and right (or equivalently their squares); whichever is larger gets written to the current write position and that pointer moves inward. The key insight is that the largest square has to come from one of the two ends because the input is sorted, so picking from the outside and writing backward guarantees a sorted output in a single pass without an extra sort.
Complexity
- Time
- O(n)
- Space
- O(n)
Related patterns
- two-pointers
Related problems
- 75. Sort Colors
- 88. Merge Sorted Array
- 905. Sort Array By Parity
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Apple
More Arrays practice problems
- 1. Two Sum
- 11. Container With Most Water
- 15. 3Sum
- 26. Remove Duplicates from Sorted Array
- 31. Next Permutation
- 41. First Missing Positive
- 48. Rotate Image
- 53. Maximum Subarray