Sorted Squared Array with Time and Space Complexity — Competitive Programming

Code Wrestling — Competitive Programming — Sorted Squared Array

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store