SQUARING A SORTED ARRAY

Problem Statement

Given a sorted array, create a new array containing squares of all the number of the input array in the sorted order.

Example 1:

Input: [-2, –1, 0, 2, 3]

Output: [0, 1, 4, 4, 9]

Example 2:

Input: [-3, –1, 0, 1, 2]

Output: [0 1 1 4 9]

Solution 1

One simple solution is to loop through the array elements and square them in place and then store the sorted squared array in output squares array and return it.

Javascript code below:-

1

2
function make_squares(arr) {
3
squares = []
4
// TODO: Write your code here
5
arr = arr.map(item=>item*item);
6
squares = arr.sort((a,b)=>a-b);
7
return squares;
8
};
9
​
10
document.write(Squares: ${make_squares([-2, -1, 0, 2, 3])}<br/>);
11
document.write(Squares: ${make_squares([-3, -1, 0, 1, 2])}<br/>);
12

13
​

Time complexity

The time complexity of the above algorithm will be O(N log N) as we are first sorting the array and then iterating the input array only once.

Space complexity

The space complexity of the above algorithm will also be O(N); this space will be used for the output array.

The above solution works but isn’t efficient as we are sorting and then iterating through the array again to store it in squares array. Better solution would be to use a 2 pointer approach and binary search mechanism to insert the squared elements in a sorted way as we iterate through the array.

Solution 2

This question becomes tricky because the array has negative numbers as well. An easier approach could be to first find the index of the first non-negative number in the array. After that, we can use Two Pointers to iterate the array. One pointer will move forward to iterate the non-negative numbers and the other pointer will move backward to iterate the negative numbers. At any step, whichever number gives us a bigger square will be added to the output array.

For the above-mentioned Example-1, we will do something like this:

Squared Sorted Array
Squared Sorted Array1

Since the numbers at both the ends can give us the largest square, an alternate approach could be to use two pointers starting at both the ends of the input array to iterate faster. At any step, whichever pointer gives us the bigger square we add it to the result array and move to the next/previous number according to the pointer. For the above-mentioned Example-1, we will do something like this:

Squared sorted array 2
Squared sorted array 2

Javascript code below:-

1

2
function make_squares(arr) {
3
const n = arr.length;
4
squares = Array(n).fill(0);
5
let highestSquareIdx = n - 1;
6
let left = 0,
7
right = n - 1;
8
while (left <= right) {
9
let leftSquare = arr[left] * arr[left],
10
rightSquare = arr[right] * arr[right];
11
if (leftSquare > rightSquare) {
12
squares[highestSquareIdx] = leftSquare;
13
left += 1;
14
} else {
15
squares[highestSquareIdx] = rightSquare;
16
right -= 1;
17
}
18
highestSquareIdx -= 1;
19
}
20
​
21
return squares;
22
}
23
​
24
​
25
document.write(Squares: ${make_squares([-2, -1, 0, 2, 3])}<br/>);
26
document.write(Squares: ${make_squares([-3, -1, 0, 1, 2])}<br/>);
27

Time complexity

The time complexity of the above algorithm will be O(N) as we sorting and squaring the array in the same iteration.

Space complexity

The space complexity of the above algorithm will also be O(N); this space will be used for the output array.

Posted from my blog with SteemPress : https://www.golibrary.