Given an array of integers
A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
Ais sorted in non-decreasing order.
sort()method to sort the transformed array in-place in ascending order.
The time complexity of above solution is O(n log n), which is not ideal. How can we optimized the solution? The problem states that the given array is sorted in ascending order. Can we use it to improve the time complexity?
The sorted in ascending order given array makes it easy to see that by the absolute value, the largest numbers are at the beginning and the end of the given array, and values are decreasing to the middle. So we can consider two pointers approach. One from the start and one from the end.
The time complexity of the two pointers is O(n).