Given an array of integers nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Table of Contents
Sample Input and Expected Output:
Input:
nums = [-4, -1, 0, 3, 10]
Output:
Squares of the sorted array: [0, 1, 9, 16, 100]
Input:
nums = [-7, -3, 2, 3, 11]
Output:
Squares of the sorted array: [4, 9, 9, 49, 121]
Solution in C++:
The idea is to use a two-pointer approach. We use two pointers, left at the beginning of the array and right at the end of the array. We compare the absolute values of the elements at these pointers and add the square of the larger absolute value to the result array from right to left. We move the appropriate pointer based on which absolute value is larger until all elements are processed.
#include <iostream>
#include <vector>
std::vector<int> sortedSquares(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> result(n); // Result array to store the squares of sorted elements.
int left = 0;
int right = n - 1;
int idx = n - 1; // Index for filling the result array from right to left.
while (left <= right) {
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if (leftSquare >= rightSquare) {
result[idx] = leftSquare;
left++; // Move left pointer to the right.
} else {
result[idx] = rightSquare;
right--; // Move right pointer to the left.
}
idx--; // Move to the next index in the result array.
}
return result;
}
int main() {
std::vector<int> nums1 = {-4, -1, 0, 3, 10};
std::vector<int> nums2 = {-7, -3, 2, 3, 11};
std::vector<int> result1 = sortedSquares(nums1);
std::vector<int> result2 = sortedSquares(nums2);
std::cout << "Squares of the sorted array: [";
for (int num : result1) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
std::cout << "Squares of the sorted array: [";
for (int num : result2) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(n), where n is the size of the input vector nums. This is because we use a two-pointer approach that traverses the array once.
The space complexity is O(n), where n is the size of the input vector nums. This is because we use an additional result vector to store the squares of the sorted elements. The size of the result vector is the same as the input array, so the space complexity is linear with respect to the input size.