We have an integer array that is sorted in ascending order. We also have 3 ints 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: Input array = -1 0 1 2 3 4 and 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)

Time complexity :o(n), no extra space

__Method: Parabolic Property__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:

Apply equation on each element

Find maximum/minimum

Merge subarrays

Useful Link:

http://stackoverflow.com/questions/4551599/sorting-result-array

## No comments:

## Post a Comment