Sorted Squared Array with Time and Space Complexity — Competitive Programming

Code Wrestling — Competitive Programming — Sorted Squared Array

Question

Sample Input:

Sample Output:

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

Solution 2 with time complexity O(n) and space complexity O(n)

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

--

--

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