Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
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. In other words, the task is to square each element in the array and then return a new array that contains the squares of each element,
sorted in non-decreasing order.
Examples
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].
Can the input array contain negative numbers, or will it always be non-negative?
Can the input array contain duplicate numbers?
Can I modify the input array, or should I create a new one for the output?
Is there any time or space complexity constraint that I need to consider?
Solutions
There are multiple approaches to solving the problem of computing the squares of sorted array elements:
Sorting the squared array:
We can square each number in the input array, sort the squared array, and then return it. This approach has a time complexity of O(n log n) due to
the sorting algorithm used.
Algorithm:
Square each number in the input array.
Sort the squared array using a sorting algorithm.
Return the sorted squared array.
public int[] SortedSquares(int[] nums) {
// Square each element in the array
for (int i = 0; i < nums.Length; i++) {
nums[i] = nums[i] * nums[i];
}
// Sort the array
Array.Sort(nums);
return nums;
}
def sorted_squares(nums: List[int]) -> List[int]:
# Square each element in the array
nums = [num * num for num in nums]
# Sort the array
nums.sort()
return nums
public int[] sortedSquares(int[] nums) {
// Square each element in the array
for (int i = 0; i < nums.length; i++) {
nums[i] *= nums[i];
}
// Sort the array
Arrays.sort(nums);
return nums;
}
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// Square each element in the array
for (int i = 0; i < nums.size(); i++) {
nums[i] *= nums[i];
}
// Sort the array
sort(nums.begin(), nums.end());
return nums;
}
};
Time complexity: O(nlogn), where n is the length of the input array. This is because we need to sort the array after squaring
each element.
Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a
separate array.
Two-pointer approach:
We can use a two-pointer approach where we use two pointers, one at the beginning and one at the end of the array, and compare the squares of the
two elements pointed to by the pointers and add the larger square to a result array from the end. Then move the pointer pointing to the larger
element towards the middle of the array. Repeat this process until both pointers meet in the middle of the array. This approach has a time
complexity of O(n).
Algorithm:
Initialize two pointers, one at the beginning and one at the end of the input array.
Initialize an empty output array.
While the two pointers have not crossed each other, compare the squares of the numbers at the two pointers.
Insert the larger squared number into the output array and move the corresponding pointer accordingly.
Continue until both pointers have crossed each other.
If there are any remaining numbers to be squared in the input array, square and add them to the output array.
Return the output array.
public int[] SortedSquares(int[] nums) {
int n = nums.Length;
int[] res = new int[n];
int left = 0;
int right = n - 1;
// Iterate from the end of the array towards the beginning
for (int i = n - 1; i >= 0; i--) {
// Compare the squares of the left and right pointers
if (Math.Abs(nums[left]) > Math.Abs(nums[right])) {
res[i] = nums[left] * nums[left];
left++;
} else {
res[i] = nums[right] * nums[right];
right--;
}
}
return res;
}
def sorted_squares(nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
left = 0
right = n - 1
# Iterate from the end of the array towards the beginning
for i in range(n - 1, -1, -1):
# Compare the squares of the left and right pointers
if abs(nums[left]) > abs(nums[right]):
res[i] = nums[left] * nums[left]
left += 1
else:
res[i] = nums[right] * nums[right]
right -= 1
return res
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int left = 0;
int right = n - 1;
// Iterate from the end of the array towards the beginning
for (int i = n - 1; i >= 0; i--) {
// Compare the squares of the left and right pointers
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
res[i] = nums[left] * nums[left];
left++;
} else {
res[i] = nums[right] * nums[right];
right--;
}
}
return res;
}
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
int left = 0;
int right = n - 1;
// Iterate from the end of the array towards the beginning
for (int i = n - 1; i >= 0; i--) {
// Compare the squares of the left and right pointers
if (abs(nums[left]) > abs(nums[right])) {
res[i] = nums[left] * nums[left];
left++;
} else {
res[i] = nums[right] * nums[right];
right--;
}
}
return res;
}
};
Time complexity: O(n), where n is the length of the input array. This is because we traverse the array once with two pointers.
Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a
separate array.
Using a priority queue:
We can use a priority queue to keep track of the squared numbers, and then pop them from the queue and add them to the output array in sorted
order.
That is, we add the squares of each element in the array to a priority queue, and then remove elements from the priority queue and add them to a
result array. This approach has a time complexity of O(n log n) since adding and removing elements from a priority queue takes log(n) time.
Algorithm:
Initialize a priority queue.
Iterate through each number in the input array and add its square to the priority queue.
While the priority queue is not empty, pop the smallest element from the priority queue and add it to the output array.
Return the output array.
public int[] SortedSquares(int[] nums) {
int n = nums.Length;
int[] res = new int[n];
// Add squares of each element to the priority queue
PriorityQueue<int> pq = new PriorityQueue<int>();
foreach (int num in nums) {
pq.Add(num * num);
}
// Remove elements from the priority queue and add to the result array
for (int i = 0; i < n; i++) {
res[i] = pq.RemoveMin();
}
return res;
}
import heapq
def sorted_squares(nums: List[int]) -> List[int]:
n = len(nums)
res = []
# Add squares of each element to the priority queue
pq = []
for num in nums:
heapq.heappush(pq, num * num)
# Remove elements from the priority queue and add to the result array
for i in range(n):
res.append(heapq.heappop(pq))
return res
import java.util.PriorityQueue;
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] res = new int[n];
// Add squares
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.offer(num * num);
}
// Remove elements from the priority queue and add to the result array
for (int i = 0; i < n; i++) {
res[i] = pq.poll();
}
return res;
}
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
// Add squares of each element to the priority queue
priority_queue<int, vector<int>, greater<int>> pq;
for (int num : nums) {
pq.push(num * num);
}
// Remove elements from the priority queue and add to the result array
for (int i = 0; i < n; i++) {
res[i] = pq.top();
pq.pop();
}
return res;
}
};
Note that in the last example, we assumed that a PriorityQueue data structure is available in C#. If it's not, then we can implement one
ourselves, or use a different data structure like a SortedSet.
Time complexity: O(nlogn), where n is the length of the input array. This is because we need to insert each squared element into
the priority queue, which takes O(logn) time for each insertion, and we insert n elements.
Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a
priority queue.
Using the fact that the array is sorted:
Since the input array is sorted, we can start by finding the index of the first non-negative number in the array, and then use a two-pointer
approach to merge the squares of the numbers to the left and right of this index.
We have to find the first non-negative element in the array and use two pointers starting from this index to traverse the array. Compare the
squares of the two elements pointed to by the pointers and add the smaller square to a result array from the start. Then move the pointer pointing
to the smaller element towards the middle of the array. Repeat this process until both pointers meet.
Algorithm:
Initialize two pointers, one at this index and one at the index directly to its left.
Initialize an empty output array.
While the pointer to the left of the non-negative index is greater than or equal to 0, and the pointer to the right of the non-negative index is
less than the length of the input array, compare the squares of the numbers at the two pointers.
Insert the smaller squared number into the output array and move the corresponding pointer accordingly.
Continue until one of the pointers reaches the end of the array.
If there are any remaining numbers to be squared in the input array, square them and add them to the output array.
Return the output array.
public int[] SortedSquares(int[] nums) {
int n = nums.Length;
int[] res = new int[n];
int left = 0;
// Find the first non-negative element in the array
while (left < n && nums[left] < 0) {
left++;
}
int right = left;
left--;
int i = 0;
// Use two pointers to traverse the array
while (left >= 0 && right < n) {
if (Math.Abs(nums[left]) < Math.Abs(nums[right])) {
res[i] = nums[left] * nums[left];
left--;
} else {
res[i] = nums[right] * nums[right];
right++;
}
i++;
}
// Add any remaining elements from either side to the result array
while (left >= 0) {
res[i] = nums[left] * nums[left];
left--;
i++;
}
while (right < n) {
res[i] = nums[right] * nums[right];
right++;
i++;
}
return res;
}
def sorted_squares(nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
left = 0
# Find the first non-negative element in the array
while left < n and nums[left] < 0:
left += 1
right = left
left -= 1
i = 0
# Use two pointers to traverse the array
while left >= 0 and right < n:
if abs(nums[left]) < abs(nums[right]):
res[i] = nums[left] * nums[left]
left -= 1
else:
res[i] = nums[right] * nums[right]
right += 1
i += 1
# Add any remaining elements from either side to the result array
while left >= 0:
res[i] = nums[left] * nums[left]
left -= 1
i += 1
while right < n:
res[i] = nums[right] * nums[right]
right += 1
i += 1
return res
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int left = 0;
// Find the first non-negative element in the array
while (left < n && nums[left] < 0) {
left++;
}
int right = left;
left--;
int i = 0;
// Use two pointers to traverse the array
while (left >= 0 && right < n) {
if (Math.abs(nums[left]) < Math.abs(nums[right])) {
res[i] = nums[left] * nums[left];
left--;
} else {
res[i] = nums[right] * nums[right];
right++;
}
i++;
}
// Add any remaining elements from either side to the result array
while (left >= 0) {
res[i] = nums[left] * nums[left];
left--;
i++;
}
while (right < n) {
res[i] = nums[right] * nums[right];
right++;
i++;
}
return res;
}
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
int left = 0;
// Find the first non-negative element in the array
while (left < n && nums[left] < 0) {
left++;
}
int right = left;
left--;
int i = 0;
// Use two pointers to traverse the array
while (left >= 0 && right < n) {
if (abs(nums[left]) < nums[right]) {
res[i] = nums[left] * nums[left];
left--;
} else {
res[i] = nums[right] * nums[right];
right++;
}
i++;
}
// Add any remaining elements from either side to the result array
while (left >= 0) {
res[i] = nums[left] * nums[left];
left--;
i++;
}
while (right < n) {
res[i] = nums[right] * nums[right];
right++;
i++;
}
return res;
}
};
Time complexity: O(n), where n is the length of the input array. This is because we traverse the array once with two pointers.
Space complexity: O(n), where n is the length of the input array. This is because we need to store the squared elements in a
separate array.
The most optimal approach is
Approach 2: Two-pointer approach.
It has a time complexity of O(n), which is the best we can do for this problem, and a space complexity of O(n), which is the same as the other
approaches. It doesn't require any extra data structures like a priority queue or a heap and is easy to implement.
There may be other approaches to solving this problem as well, but these are a few common ones.
