# 360 Sort Transformed Array

Given a **sorted** array of integers `nums` and integer values `a`,`b` and `c`. Apply a quadratic function of the form `f(x) =ax2+bx+c`to each element `x` in the array.

The returned array must be in **sorted order**.

Expected time complexity:**O(n)**

**Example:**

```
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,

Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Result: [-23, -5, 1, 7]
```

**The Idea:** The first thing to recognize is that in a parabola, with `a != 0`, then ends of the parabola are symmetric about the root, and they are the largest or smallest values of f(x) depending on whether `a > 0` or `a < 0`. If we begin at the end points of `nums`, then we can simply chose the smaller one until the left if `a < 0`, on in reverse if `a > 0`. Even though there are the cases when `a=0 and b>0` or`a=0 and b<0` , both these cases can be reduced to following the same logic following when `a <= 0`.![](https://176165416-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphwLiMOHOYPmtrx%2F-LoJHq55n17qGKUSaNW0%2F-LoJIlG0xZNu6JjEnfWj%2F360%20Sort%20Transformed%20Array.png?generation=1568003868481923\&alt=media)

**Complexity:** O(n) time and constant extra space

```python
import operator


class Solution:
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """

        def quad(x):
            return (a * pow(x, 2)) + (b * x) + c

        solution = [0] * len(nums)
        def iter_forward_or_rev(start, add, cmp):
            left = 0
            right = len(nums) - 1
            while left <= right:
                if cmp(quad(nums[left]), quad(nums[right])):
                    solution[start] = quad(nums[left])
                    left += 1
                else:
                    solution[start] = quad(nums[right])
                    right -= 1
                start += add

        # if a > 0, then left of parabola are largest
        # otherwise the ends of parabola are the smallest
        if a > 0:
            iter_forward_or_rev(len(nums) - 1, -1, operator.gt)
        else:
            iter_forward_or_rev(0, 1, operator.lt)
        return solution
```