Squares of a Sorted Array - Solution & Explanation
Problem Statement
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] <= 104numsis 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?Approach Overview
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 1: Approach 1: Sorting After Squaring
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.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in place.
Approach 2: Approach 2: Two Pointer Technique
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.
Complexity
Time Complexity: O(n) as we traverse the array only once.
Space Complexity: O(n) due to the result array.
Approach 3: Two Pointers
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).
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Squares of a Sorted Array - Leetcode 977 - Python • NeetCode • 60,096 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Squares of a Sorted Array easy or hard?
Squares of a Sorted Array Python/Java solution
How to solve Squares of a Sorted Array in O(n)?
What is the best approach for Squares of a Sorted Array?
Is Squares of a Sorted Array asked at Google/Amazon/Meta?
What data structure is used in Squares of a Sorted Array?
What is the time complexity of Squares of a Sorted Array?
Ready to solve this problem?
Practice Squares of a Sorted Array with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor