Sort squares of a sorted array in linear runtime (O(n))

Given a sorted array that contains both negative and positive integers we aim to get its squares array in sorted orders. Let us understand this with an example.

Sorted array which contains both positive and negative integers.
Sorted array which contains input squares.

Let’s understand how we can solve this problem in linear time. To solve this in linear time, we have to take two handles which represent the start and end of the array.

As 11 is greater than 8, we move end to its previous index and stores last index square into end of output array.
In this case, 8 is less than 9, moving end to its previous index, and 9 square stores in the output array.
Here 8 is greater than 5 so, put the square of 8 at the current index of the output array, and moves start to its next.
In this step as 6 greater than 5 so, we store the square of 6 into the output array.

We continue doing these steps until the start index and end index meets. Once both indices meet we get our out array filled with squares in sorted order.

Now, Let’s jump right into the code for this approach.

#include <iostream>

using namespace std;

void printArray(int arr[], int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << "  ";
    }
    cout << endl;
}

int main()
{
    int input[] = {-8, -6, -3, -1, 2, 4, 5, 9, 11};
    int size = sizeof(input) / sizeof(input[0]);
    int output[size];
    int start, end, curr = size - 1;
    start = 0, end = size - 1;
    while (start <= end)
    {
        if (abs(input[start]) > abs(input[end]))
        {
            output[curr] = input[start] * input[start];
            start++;
        }
        else
        {
            output[curr] = input[end] * input[end];
            end--;
        }
        curr--;
    }
    cout << "Original Array: ";
    printArray(input, size);
    cout << "Squared Array: ";
    printArray(output, size);
    return 0;
}
// Output
Original Array: -8  -6  -3  -1  2  4  5  9  11  
Squared Array: 1  4  9  16  25  36  64  81  121

Here we are iterating the array once by maintaining the start and end of indices, so this algorithm’s runtime becomes O(n).

I hope this helps you to understand the sorted squares array problem. If you have any better solution to solve this problem, please let our readers know by commenting below. Happy Learning!.d

Advertisements