Squares of a Sorted Array
EasyPrompt
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?Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to first square every element in the input array and then sort the resulting array. This is simple to implement but not the most efficient.
Algorithm
- Create a new array
resultof the same size asnums. - Iterate through
numswith an indexifrom 0 ton-1. - For each element
nums[i], calculate its square:squared = nums[i] * nums[i]. - Store the result in the new array:
result[i] = squared. - After the loop, sort the
resultarray using a standard sorting function. - Return the sorted
resultarray.
import java.util.Arrays; class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { result[i] = nums[i] * nums[i]; } Arrays.sort(result); return result; }}Walkthrough
This method involves two main steps. First, we iterate through the input array nums from beginning to end. For each number, we calculate its square and store it in a new array, let's call it result. After this first pass, the result array will contain the squares of all elements from nums, but it will not be sorted. For example, if nums is [-4, -1, 0, 3, 10], the result array will be [16, 1, 0, 9, 100]. The second step is to sort this result array in non-decreasing order. Standard sorting algorithms like Merge Sort or Quick Sort can be used, which typically have a time complexity of O(n log n). After sorting, result becomes [0, 1, 9, 16, 100], which is the final answer.
Complexity
Time
O(n log n), where n is the number of elements in the array. Squaring each element takes O(n) time, and sorting the resulting array takes O(n log n) time. The sorting step dominates the complexity.
Space
O(n) or O(log n). We need O(n) space for the new array to store the squares. The space complexity of `Arrays.sort()` in Java for primitives is O(log n) due to its dual-pivot quicksort implementation. Thus, the total space is dominated by the O(n) output array.
Trade-offs
Pros
Simple to understand and implement.
Cons
Not the most efficient solution as it doesn't utilize the fact that the input array is already sorted.
The O(n log n) time complexity can be improved upon.
A more optimal approach uses two pointers to build the sorted result array in a single pass, achieving linear time complexity. This method leverages the sorted nature of the input array.
Algorithm
- Initialize
nas the length of the input arraynums. - Create a new integer array
resultof sizen. - Initialize a
leftpointer to 0 and arightpointer ton-1. - Iterate with a pointer
pfromn-1down to 0 (this will be the index for theresultarray). - Inside the loop, compare the absolute value of
nums[left]andnums[right]. - If
abs(nums[left])is greater thanabs(nums[right]), the square ofnums[left]is larger. Place this square atresult[p]and incrementleft. - Otherwise, the square of
nums[right]is greater or equal. Place its square atresult[p]and decrementright. - Decrement
pin each iteration. - After the loop finishes, return the
resultarray.
class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; int left = 0; int right = n - 1; for (int p = n - 1; p >= 0; p--) { if (Math.abs(nums[left]) > Math.abs(nums[right])) { result[p] = nums[left] * nums[left]; left++; } else { result[p] = nums[right] * nums[right]; right--; } } return result; }}Walkthrough
Since the input array nums is sorted, the numbers with the largest absolute values are at the ends of the array. Consequently, their squares will be the largest values in the final sorted array. We can use this property to our advantage.
We initialize two pointers, left at the start (index 0) and right at the end (index n-1) of the input array. We also create a result array of the same size. We'll fill the result array from right to left, starting with the largest square.
In each step, we compare the absolute values of nums[left] and nums[right]. The number with the larger absolute value will produce a larger square. We place this larger square at the current end of the result array (indicated by a third pointer, p), and then move the corresponding pointer (left or right) inward. We continue this process until the pointers meet or cross, at which point the result array will be completely filled with the squared values in sorted order.
Complexity
Time
O(n), where n is the number of elements in the array. The two pointers `left` and `right` traverse the array once, so the algorithm runs in linear time.
Space
O(n), for the output array. If the output array is not considered extra space, the complexity is O(1) as we only use a few variables as pointers.
Trade-offs
Pros
Optimal time complexity of O(n).
Efficiently uses the sorted property of the input array in a single pass.
Cons
Slightly more complex to reason about and implement compared to the brute-force approach.
Solutions
Solution
class Solution {public int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; for (int i = 0, j = n - 1, k = n - 1; i <= j;) { if (nums[i] * nums[i] > nums[j] * nums[j]) { res[k--] = nums[i] * nums[i]; ++i; } else { res[k--] = nums[j] * nums[j]; --j; } } return res; }}/** * @param {number[]} nums * @return {number[]} */ var sortedSquares = function (nums) { const n = nums.length; const res = new Array(n); for (let i = 0, j = n - 1, k = n - 1; i <= j; ) { if (nums[i] * nums[i] > nums[j] * nums[j]) { res[k--] = nums[i] * nums[i]; ++i; } else { res[k--] = nums[j] * nums[j]; --j; } } return res; };class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n i, j, k = 0, n - 1, n - 1 while i <= j: if nums[i] * nums[i] > nums[j] * nums[j]: res[k] = nums[i] * nums[i] i += 1 else: res[k] = nums[j] * nums[j] j -= 1 k -= 1 return resclass Solution {public: vector<int> sortedSquares(vector<int> &nums) { int n = nums.size(); vector<int> res(n); for (int i = 0, j = n - 1, k = n - 1; i <= j;) { if (nums[i] * nums[i] > nums[j] * nums[j]) { res[k--] = nums[i] * nums[i]; ++i; } else { res[k--] = nums[j] * nums[j]; --j; } } return res; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.