JavaScript Algorithm: How to Square a Sorted Array
Problem
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.
Example 1:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]Example 2:
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]Note:
1 <= A.length <= 10000-10000 <= A[i] <= 10000Ais sorted in non-decreasing order.
Solution
Brute Force
First, loop through the given array, and return the squared element. Like in example one, [-4, -1, 0, 3, 10] becomes [16, 1, 0, 9, 100]. After we squared all elements, we can use JavaScript array 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?
Two-Pointers
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).
Resources:
