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.
1def sorted_squares(nums):
2 nums = [num * num for num in nums]
3 nums.sort()
4 return nums
5
6nums = [-4, -1, 0, 3, 10]
7print(sorted_squares(nums))
8This Python solution utilizes list comprehensions to square each element, followed by the built-in sort() method that sorts the array in place.
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
In this solution, two pointers start at the ends of the array. The larger square from the two ends is added to the result array from the last position to the first, effectively sorting as we fill the array.