Sponsored
Sponsored
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in place.
1#include <stdio.h>
2#include <stdlib.h>
3
4int cmp(const void *a, const void *b) {
5 return (*(int *)a - *(int *)b);
6}
7
8void sortedSquares(int* nums, int numsSize, int* returnSize) {
9 for (int i = 0; i < numsSize; i++) {
10 nums[i] = nums[i] * nums[i];
11 }
12 qsort(nums, numsSize, sizeof(int), cmp);
13 *returnSize = numsSize;
14}
15
16int main() {
17 int nums[] = {-4, -1, 0, 3, 10};
18 int numsSize = sizeof(nums) / sizeof(nums[0]);
19 int returnSize;
20 sortedSquares(nums, numsSize, &returnSize);
21 for (int i = 0; i < returnSize; i++) {
22 printf("%d ", nums[i]);
23 }
24 return 0;
25}
26In 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.
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.
Time Complexity: O(n) as we traverse the array only once.
Space Complexity: O(n) due to the result array.
1
public class Solution {
public static int[] SortedSquares(int[] nums) {
int n = nums.Length;
int[] result = new int[n];
int left = 0, right = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (Math.Abs(nums[left]) < Math.Abs(nums[right])) {
result[i] = nums[right] * nums[right];
right--;
} else {
result[i] = nums[left] * nums[left];
left++;
}
}
return result;
}
public static void Main() {
int[] nums = {-4, -1, 0, 3, 10};
int[] result = SortedSquares(nums);
Console.WriteLine(string.Join(" ", result));
}
}
This C# solution takes advantage of the two-pointer strategy to build an ordered squared array efficiently by comparing endpoints and filling the resultant array from its end.