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.
This approach involves first squaring every element, and then sorting the resultant array. Since the sorting algorithm typically used is O(n log n) in terms of time complexity, this approach is straightforward but not the most optimal for this problem.
In this solution, we first compute the square of each element in the array. Thereafter, we use the qsort function from the standard library to sort the squared elements. This approach directly modifies the input array.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in place.
Utilizing a two-pointer technique allows us to traverse the array from both ends, taking advantage of the non-decreasing order of the input array. By comparing the squares of elements from both ends, we can construct the output array from the largest to the smallest square, ensuring an O(n) time complexity.
In this solution, two pointers start at the ends of the array. The larger square from the two ends is added to the result array from the last position to the first, effectively sorting as we fill the array.
Time Complexity: O(n) as we traverse the array only once.
Space Complexity: O(n) due to the result array.
Since the array nums is already sorted in non-decreasing order, the square values of the negative numbers in the array are decreasing, and the square values of the positive numbers are increasing. We can use two pointers, each pointing to the ends of the array. Each time we compare the square values of the elements pointed to by the two pointers, we put the larger square value at the end of the result array.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Sorting After Squaring | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Two Pointer Technique | Time Complexity: O(n) as we traverse the array only once. |
| Two Pointers | — |
| 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 |
Squares of a Sorted Array - Leetcode 977 - Python • NeetCode • 57,822 views views
Watch 9 more video solutions →Practice Squares of a Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor