# Question

Write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

# Sample Input:

array = [1, 2, 3, 5, 6, 8, 9]

# Sample Output:

[1, 4, 9, 25, 36, 64, 81]

# Solution

`private int[] GetSquaredSortedArray(int[] arr){     // Time complexity - O(n logn)     // Space Complexity - O(n)     int[] arrSquares = new int[arr.Length];     for (int i = 0; i < arr.Length; i++)     {        arrSquares[i] = arr[i] * arr[i];     }     Array.Sort(arrSquares);     return arrSquares;}`

So let’s try to avoid sorting the array at the end. And when finding the squares of number, at that time itself, place it at the right place such that the array always remains sorted.

We will keep two flags one for storing a smaller value index and another one for storing a larger value index. Since the array is already sorted, initially the smallerValueIndex = 0 and largerValueIndex = (length of array) — 1.
Along with that we will have an array to store the sorted values, let’s name it as sortedSquares.

Iterate over the array and then compare the absolute value of the number at smallerValueIndex and largerValueIndex.
(Don’t know absolute value? So in simple terms, absolute value of -2, means |-2| and it is equal to 2. Basically removing the minus(-) sign).

If | array[smallerValueIndex] | > | array[largerValueIndex] |, then store the square value of array[smallerValueIndex] at last available slot of sortedSquares (the array) and increase the value of smallerValueIndex.

Else, store the square value of array[largerValueIndex] at last available slot of sortedSquares (the array) and decrease the value of largerValueIndex.

`private int[] GetSquaredSortedArray(int[] arr){    // Time Complexity - O(n)    // Space Complexity - O(n)    int[] sortedSquares = new int[arr.Length];    int smallerValueIndex = 0;    int largerValueIndex = arr.Length - 1;    for (int i = arr.Length - 1; i >= 0; i--)    {       // i is used for storing the value in sortedSquares array       int smallerValue = arr[smallerValueIndex];       int largerValue = arr[largerValueIndex];       if (Math.Abs(smallerValue) > Math.Abs(largerValue))       {            sortedSquares[i] = smallerValue * smallerValue;            smallerValueIndex++;       }       else       {            sortedSquares[i] = largerValue * largerValue;            largerValueIndex--;       }    }    return sortedSquares;}`

--

--