Sorted Squared Array

Brute force approach

The brute force approach is quite intuitive and simple and follows the below steps:

1. Since the array is already sorted, create a new array called result and initialize its length to be the same as the input array
2. Square every value in the given array and store the results in the result array.
3. Sort the result array again (since input array can have negative integers as well, it might be the case the there are some negative integers and their squares will be positive, hence disturbing the sorted order).
4. Return results array.

Time and Space complexity

• Time: O(nlogn) - To sort the array, where n is the number of integers in the given array.
• Space: O(n) - For the results array.

Two Pointer approach

To iterate over the array and compare greater / smaller values, we are going to initialize two pointers, start and end.

1. Create an array results and initialize with the length of the input array.
2. Declare two pointers - start and end. Initialize start to the start i.e. arr[0] and end to the end - i.e. arr[length - 1]
3. Declare a third pointer k and initialize it to the end of the array - This is to keep track of where to put the number in the resulting array. We will be inserting values into the array from the end.
4. While start is less than end, check if the ABSOLUTE value of start number is LESS than or EQUAL to ABSOLUTE value of end number. If that is the case, we can square the end number and push it to the end of the result array, decrementing end (end--) and k (k--).
5. By doing point number 4, we essentially got the largest square of the array, we push it at the end.
6. IF arr[start] > arr[end], we simply square and push the start element while decrement k and start to search for the next value.
7. Return result at the end.

Time and Space complexity

• Time: O(n) - Since we are going to iterate over the array only once (at max)
• Space: O(n) - Because of the result array.

Javascript based solution - Brute Force

This solution is based towards javascript implementation of the problem using map() and sort(). It is a Brute Force Solution (As discussed in the first solution) but with a simpler syntax (JS devs would agree).

1. Map over the input array to create a new squared array
2. Return the sorted order.