FOR FREE YEAR SOLVED

Given an array of integers A sorted in non-decreasing order, return an array of the square of each number, also in sorted non-decreasing order.

Note:

We can solve the question by squaring each elemnt and then sort the array. 

For this question each element takes O(n) time & sorting the list takes O(n log n) time

The overall Time Complexity will be O(n) + O(n log n) ≅ O(n log n)

Better Approach

We can solve the problem using two pointer technique which will reduce the time complexity to O(n)

Example

Step 1: We will create a new array of the same length which will be initialized with 0’s.

Step 2: we will main two pointers one at first and one at last. As the array will be sorted we will place the largest at last index.

             s = 0

            e = len(a) – 1

            k = len(a) – 1 / last index

Step 3:  Run a loop while s <= e

Step 4:  If  the absolute value of A[s] > = abs(A[e]) 

                       fill A[k] = A[s] * A[s]

                       increment s by 1

               else

                        fill A[k] = A[e] * A[e]

                        decrement e by 1

 This is only possible as the values given are sorted non decreasing order.

Step 5: Decrement index k by 1

Step 6: Repeat Step 3 to Step 5 until the loop condition fails.

Step 7: Return the new array.