Watch 10 video solutions for Squares of a Sorted Array, a easy level problem involving Array, Two Pointers, Sorting. This walkthrough by NeetCode has 57,822 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10] Output: [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:
Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums is sorted in non-decreasing order.Follow up: Squaring each element and sorting the new array is very trivial, could you find an
O(n) solution using a different approach?Problem Overview: Given a non-decreasing sorted integer array nums, return a new array containing the squares of each number, also sorted in non-decreasing order. The challenge comes from negative values: squaring them can produce larger values than some positive numbers.
Approach 1: Sorting After Squaring (O(n log n) time, O(1) or O(n) space)
The most direct strategy is to square every element in the array and then sort the result. Iterate through nums, replace each value with its square using x * x, then run a standard sorting algorithm on the array. This works because sorting reorders the squared values correctly regardless of the original sign of the numbers. The implementation is simple and easy to reason about, but the sorting step dominates the runtime at O(n log n). Prefer this approach when clarity matters more than optimal performance or when you want a quick baseline solution.
Approach 2: Two Pointer Technique (O(n) time, O(n) space)
The optimal solution uses the structure of the sorted array. The largest square must come from either the most negative value on the left or the largest positive value on the right. Use two pointers: one at the start (left) and one at the end (right). Compare nums[left]^2 and nums[right]^2, place the larger square at the end of the result array, and move the corresponding pointer inward. Continue filling the result array from right to left. Each element is processed exactly once, giving O(n) time and O(n) extra space for the output array. This pattern frequently appears in problems involving sorted arrays and symmetric comparisons.
The key insight is that squaring breaks the sorted order only because negative values flip sign. The largest magnitude values sit at the edges of the array. A two pointers strategy lets you compare those extremes directly without re-sorting.
Recommended for interviews: Interviewers expect the Two Pointer Technique. The sorting approach shows you understand the problem but misses the optimization opportunity. Using two pointers demonstrates that you recognize patterns in a sorted array and can avoid unnecessary sorting. The optimal solution runs in linear time, processes each element once, and is considered the standard interview answer.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting After Squaring | O(n log n) | O(1) to O(n) | Simple baseline solution or when using built-in sort is acceptable |
| Two Pointer Technique | O(n) | O(n) | Optimal approach when the input array is already sorted |