Squares Of A Sorted Array

Problem

Given an array of numbers sorted in increasing order, generate another array containing the square of all the elements in the given array, sorted in increasing order.

Example 1

{
"numbers": [1, 2, 3, 4]
}

Output:

[1, 4, 9, 16]

Example 2

{
"numbers": [-9, -5, -2, 0, 3, 7]
}

Output:

[0, 4, 9, 25, 49, 81]

Solution

function generate_sorted_array_of_squares(numbers) {
    let result = [];
    // Left and right pointer
    let l = 0;
    let r = numbers.length - 1;
    // Position to add squared number to A
    let p = r;

    // Add the higher number to the array and then decrease the pointer
    while (l <= r) {
        if (numbers[l] ** 2 > numbers[r] ** 2) {
            result[p--] = numbers[l++] ** 2;
        } else {
            result[p--] = numbers[r--] ** 2;
        }
    }

    return result;
}

Time and Space Complexity

Time Complexity : O(n)
Space Complexity: O(n)