Polar_'s blog

Wondering if there is a better solution
By Polar_, history, 2 years ago, In English

I found this on leetcode someone posted the problem . I am wondering if there is a solution for followup .
Given a calculation class where you initialize values for $$$a,b,c$$$ and the following function $$$f(x) = ax^2 + bx + c$$$, and a list of numbers, apply this function to all values in the list. 

class Calculation {
int a;
int b;
int c;

int[] calculate(int[] arr)
}

Followup: We want the output array to be sorted. Can we do better than $$$O(nlogn)$$$?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Your problem is simply the same as sorting an array, which is not faster than n log n if it is a comparison-based sort.

You can use Radix sort or Count sort to break the lower bound based on comparison sorting.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah . I was thinking the same . Thanks for your input .

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the initial list of numbers is already sorted, then you can solve this in $$$O(n)$$$ time.

Since $$$ax^2 + bx + c$$$ is a quadratic function, it either increases until some point and then decreases (if $$$a < 0$$$) or it decreases until some point and then increases (if $$$a > 0$$$). This critical point can be found through the first derivative, i.e., $$$2ax + b = 0$$$, which solves to $$$x = \frac{-b}{2a}$$$.

So the algorithm works like this, assuming the array of numbers is sorted in non-decreasing order:

  • Calculate the critical point $$$x = \frac{-b}{2a}$$$, and implicitly partition the array based on this point, e.g., save the index in which all elements before this index are smaller than $$$\frac{-b}{2a}$$$ and all elements after or equal to this index are greater than or equal to $$$\frac{-b}{2a}$$$.
  • Apply the function to each element of the array (this can be done while looking for the critical point too).
  • If $$$a > 0$$$, then the right partition will be in increasing order and the left partition will be in decreasing order. For $$$a < 0$$$, it's the opposite. Now reverse the appropriate partition so that both are in increasing order.
  • Perform the merge function (cannot be done efficiently in-place, so you'll need another array) to merge these two sorted array partitions.

Complexity: $$$O(n)$$$ runtime, $$$O(n)$$$ auxiliary space

→ Reply