Sorted Squared Array with Time and Space Complexity — Competitive Programming

Question — 3 (Level — Easy)

Code Wrestling — Competitive Programming — Sorted Squared Array

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve another easy problem, Sorted Squared Array.

We will find the Time and Space complexity of our solution and will also guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Github Repository Link: Github/SortedSquaredArray

Go to the previous question → Question — 2 (Validate Subsequence)

Go to the next question → Question — 4 (Tournament Winner)

Code Wrestling

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]

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

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

Note: The array contains integers, which means it can have negative numbers, so if we find the square of a negative number it will be a positive number and that’s where we have to be a little careful.

Solution 1 with time complexity O(n logn) and space complexity O(n)

Approach:

Just find the square of an array by looping over each and every element and store the value in a new array and then sort it using the fastest sorting algorithm (quickSort).

Let’s understand it directly through the code snippet: (Github Link)

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

Here the time complexity is O(n logn) because the sorting has a time complexity of O(n logn) and the for loop has a time complexity of O(n), now add both so O(n + n logn) => O(n logn) and space complexity is O(n) because we are storing the squared numbers in another array, thus O(n).

Let’s think of a way that we can reduce the time complexity. Maybe by avoiding sorting at the end?

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

Approach:

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.

array = [ -5, -3, -2, 0, 1, 2, 3 ]

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.

Let’s see the code snippet (C#): (Github Link)

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

Here the time complexity is O(n) and space complexity is O(n).

Github Repository Link: Github/SortedSquaredArray

Go to the previous question → Question — 2 (Validate Subsequence)

Go to the next question → Question — 4 (Tournament Winner)

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.

Code Wrestling