Because the input is sorted and the function is a second degree polynomial, simply applying the function will result in at most two increasing/decreasing runs. Which Python's sort function will recognize and simply reverse/merge in O(n).
def sortTransformedArray(self, nums, a, b, c): return sorted(a*x*x + b*x + c for x in nums)
@sindhuri You mean it should be "easy"? Nah... not all languages offer this luxury, and even if they do, you need to know about it and how to use it (Java for example offers it, but only for
Integer, not for
int). The "regular" way to solve this problem is like most people have done it, and I find "medium" appropriate.
Could you please elaborate how does Python handle the reverse/merge in O(n)? Appreciate it.
@wei89 Did you read the Wikipedia article? If you did and it's not enough, check out its "External links".
Thank you so much!!! I didn't realized that there was the link. But thanks. I used this method to solve the "median of two sorted array" in O(m+n), this is awesome! Thanks.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.