# Sorted Squared Array with Time and Space Complexity — Competitive Programming Code Wrestling — Competitive Programming — Sorted Squared Array

# Solution

The main objective here is to find the square of the given array and it should again be sorted.

`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;}`

## Approach:

1. Let’s create a new array variable, sortedSquares, and have two flags, smallerValueIndex = 0, largerValueIndex = (length of array) — 1 => 6.
2. Now we will insert the vales in sortedSquares, but in reverse order, that means we will insert the last element first and then will go down all the way to zero, that means inserting first element.
3. Iterate over the whole array as index i, starting with last index of array and decreasing it to zero. Basically a for loop starting from arrayLength -1, to whole the way to 0. Thus at first i = arrayLength — 1; => 6
4. Now compare the absolute value of the number at smallerValueIndex and largerValueIndex.
5. If | array[smallerValueIndex] | > | array[largerValueIndex] |, sortedSquares[i] = (array[smallerValueIndex])² and smallerValueIndex++, otherwise
6. sortedSquares[i] = (array[largerValueIndex])² and largerValueIndex— — .
7. Repeat Step — 3 to 6, until loop finishes.
`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;}`

--

--