Apply a funtion on sorted array

  • 1

    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 with O(n) time?

  • 0
    the question is rather easy, you know the f(x) is a parabolic curve, 
    you first need to figure out the x-axis of the highest/lowest point,
    and then count number one by one from the lowest or from two end of 
    the array

  • 3

    a*x^2 + b * x + c is monotonically increasing or decreasing on the two side of x_mid == -b / 2a. so if the number in the input array is all to the left or right of x_mid, the function would still remain sorted. If the number s in the input array overlap with x_mid, then starting from both end, the number with distance furthest to x_mid should be evaluated first.

    a == 0 is a special case where the function become linear, and the resulting array is sorted.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.