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
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.
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.
1public class Solution {
2 public static int[] sortedSquares(int[] nums) {
3 int n = nums.length;
4 int[] result = new int[n];
5 int left = 0, right = n - 1;
6 for (int i = n - 1; i >= 0; i--) {
7 if (Math.abs(nums[left]) < Math.abs(nums[right])) {
8 result[i] = nums[right] * nums[right];
9 right--;
10 } else {
11 result[i] = nums[left] * nums[left];
12 left++;
13 }
14 }
15 return result;
16 }
17
18 public static void main(String[] args) {
19 int[] nums = {-4, -1, 0, 3, 10};
20 int[] result = sortedSquares(nums);
21 for (int num : result) {
22 System.out.print(num + " ");
23 }
24 }
25}
26This Java code uses two pointers starting from the ends of the array. It chooses the bigger square to place at the highest available index in a new result array. After placing it, the pointer moves towards each other. This results in a direct O(n) solution.