Applying a function on sorted array

Question

Taken from the google interview question here

Suppose that you have a sorted array of integers (positive or negative). You want to apply a function of the form f(x) = a * x^2 + b * x + c to each element x of the array such that the resulting array is still sorted. Implement this in Java or C++. The input are the initial sorted array and the function parameters (a, b and c).

Do you think we can do it in-place with less than O(n log(n)) time where n is the array size (e.g. apply a function to each element of an array, after that sort the array)?

Answer 1

I think this can be done in linear time. Because the function is quadratic it will form a parabola, ie the values decrease (assuming a positive value for 'a') down to some minimum point and then after that will increase. So the algorithm should iterate over the sorted values until we reach/pass the minimum point of the function (which can be determined by a simple differentiation) and then for each value after the minimum it should just walk backward through the earlier values looking for the correct place to insert that value. Using a linked list would allow items to be moved around in-place.

Answer 2

The quadratic transform can cause part of the values to "fold" over the others. You will have to reverse their order, which can easily be done in-place, but then you will need to merge the two sequences.

In-place merge in linear time is possible, but this is a difficult process, normally out of the scope of an interview question (unless for a Teacher's position in Algorithmics).

Have a look at this solution: http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/Huang88.pdf

I guess that the main idea is to reserve a part of the array where you allow swaps that scramble the data it contains. You use it to perform partial merges on the rest of the array and in the end you sort back the data. (The merging buffer must be small enough that it doesn't take more than O(N) to sort it.)

Answer 3

If a is > 0, then a minimum occurs at x = -b/(2a), and values will be copied to the output array in forward order from [0] to [n-1]. If a < 0, then a maximum occurs at x = -b/(2a) and values will be copied to the output array in reverse order from [n-1] to [0]. (If a == 0, then if b > 0, do a forward copy, if b < 0, do a reverse copy, If a == b == 0, nothing needs to be done). I think the sorted array can be binary searched for the closest value to -b/(2a) in O(log2(n)) (otherwise it's O(n)). Then this value is copied to the output array and the values before (decrementing index or pointer) and after (incrementing index or pointer) are merged into the output array, taking O(n) time.

Answer 4

static void sortArray(int arr[], int n, int A, int B, int C)
    {
       // Apply equation on all elements
        for (int i = 0; i < n; i++)
            arr[i] = A*arr[i]*arr[i] + B*arr[i] + C;

        // Find maximum element in resultant array
        int index=-1;
        int maximum = -999999;
        for (int i = 0; i< n; i++)
        {
            if (maximum < arr[i])
            {
                index = i;
                maximum = arr[i];
            }
        }

        // Use maximum element as a break point
        // and merge both subarrays usin simple
        // merge function of merge sort
        int i = 0, j = n-1;
        int[] new_arr = new int[n];
        int k = 0;
        while (i < index && j > index)
        {
            if (arr[i] < arr[j])
                new_arr[k++] = arr[i++];
            else
                new_arr[k++] = arr[j--];
        }

        // Merge remaining elements
        while (i < index)
            new_arr[k++] = arr[i++];
        while (j > index)
            new_arr[k++] = arr[j--];

        new_arr[n-1] = maximum;

        // Modify original array
        for (int p = 0; p < n ; p++)
            arr[p] = new_arr[p];
    }