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.
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.
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