Day-3 Squaring a Sorted Array

Hello, Today we shall solve a problem where we are given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.

Any thoughts on how to solve this already ?

Great, for this problem we will use a Two-pointer type solution. Before that, we shall understand the question. Here we are given an array say arr which contains any integers. And asked to return an array of the squares of the elements in the arr in a sorted manner. Now I hope you understand the problem statement.

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]

Now let's see how can we solve this problem ? This is an easy question to answer. The only difficulty is that we can have negative integers in the input array, which makes generating the output array with squares in sorted order a little more difficult.

Finding the index of the first non-negative number in the array might be a simpler technique. After that, we may iterate the array with Two Pointers. The non-negative numbers will be iterated with one pointer moving ahead, while the negative numbers will be iterated with the other pointer moving backward. At any point in the process, the number that results in a larger square will be added to the output array.

But there is one more solution, which is much better than the one mentioned above.

An alternative technique may be to apply two pointers beginning at each end of the input array, as the numbers at both ends can give us the biggest square. At any point in the process, we add the larger square to the result array and advance to the next/previous number indicated by the pointer.

• Create an array for the results and fill it with 0s initially
• Then create a variable say square_index for storing the last index of the result array and set it to length - 1 .
• Then take two pointers say right_pointer left_pointer and set length(array) -1 , 0 respectively
• Then check which of the left pointer square is greater or the right square. And then insert in the result array and increment the pointers when the condition is reached and also increment the square_index

Let's See the code in python3

def square_elemnts(arr):

    result_arr = [0 for i in range(len(arr))]
    left_pointer = 0
    square_index = len(arr) - 1
    right_pointer = len(arr) - 1
    while left_pointer <= right_pointer:
        squareleft = arr[left_pointer] * arr[left_pointer]
        squareright = arr[right_pointer] * arr[right_pointer]
        if squareleft > squareright:
            result_arr[square_index] = squareleft
            left_pointer += 1
        else:
            result_arr[square_index] = squareright
            right_pointer -= 1
        square_index -= 1
    return result_arr


print(square_elemnts([-2, -1, 0, 2, 3]))

result:[0, 1, 4, 9, 16]