Python one-liner

• 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)``````

• Exactly!Why would this be in medium difficulty level?

• @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.

• Ok, but you do realize you're supposed to solve that one in O(log(m+n)), right?

• Yes. Doing it right now. Thanks!

• Well, I hope interviewer can let me pass if I explained this...

• I have no idea why would people down vote my genuine doubt.

• because of the timsort. Thank you Tim Peter

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