Squares of a Sorted Array
The key idea
The input is already sorted, so the largest square always sits at one of the two ends (the most negative or the most positive value). Walk two pointers inward from both ends, take the bigger square each step, and fill the answer from the back. This skips the re-sort entirely.
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.
The twist is that nums may contain negative numbers, so a negative value with a large magnitude squares to a large positive number. Because the array is already sorted, the biggest squares live at the two ends — can you build the answer in O(n) time without sorting again?
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4numsis sorted in non-decreasing order
Examples
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Next PermutationMEDIUM
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY