Sorting result array

Question

I was asked this question in Adobe interview:

We have an integer array that is sorted in ascending order. We also have 3 integers A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and return the corresponding sorted array.

Example I was given:

Input array = -1 0 1 2 3 4
A = -1, B = 2, C = -1`

Result of applying the formula to each element = -4 -1 0 -1 -4 -9
So expected result = -9 -4 -4 -1 -1 0 (sorted)

My best solution was to apply formula and sort it resulting in O(nlogn) solution. I could not do it better.

Any guidance in improving it is helpful.

Answer 1

The equation given is parabolic. So the result of applying it to a sorted array will result in an array that will have a maximum/minimum with the sub-arrays to its left and right sorted.

In your case the maximum is 0 and the sub array to its left [-4 -1] is sorted in ascending order and the sub-array to its right [-1 -4 -9] is sorted in descending order.

All you need to do is merge these sorted arrays which is linear in time.

So the algorithm is:

1. Apply equation on each element
2. Find maximum/minimum
3. Merge subarrays