Problem statement

https://leetcode.com/problems/sort-transformed-array/

Solution

Similar to Problem 0977. Squares of a Sorted Array, we can notice that the first half decreasing and second increasing or in the opposite direction. Actually python sort function smart enough to sort data like given in liner time.

Complexity

Time complexity is $O(n)$, space complexity is $O(n)$.

Code

class Solution:
    def sortTransformedArray(self, nums, a, b, c):
        if a == 0 and b >= 0: return [b*x+c for x in nums]
        if a == 0 and b <  0: return [b*x+c for x in nums[::-1]]
        p1 = [a*x*x+b*x+c for x in nums if x < -b/2/a]
        p2 = [a*x*x+b*x+c for x in nums if x >= -b/2/a]
        if a > 0: return sorted(p1[::-1] + p2)
        if a < 0: return sorted(p2[::-1] + p1)