## 360. Sort Transformed Array

Given asortedarray of integersnumsand integer valuesa,bandc. Apply a quadratic function of the form f(x) =ax2+bx+cto each elementxin the array.

The returned array must be insorted order.

Expected time complexity:O(n)

Example 1:

``````Input:
nums =
[-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]
``````

Example 2:

``````Input:
nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]
``````

Thoughts:

1. Identify & utilize the convexity & concavity of the quadratic function based on a value
2. Use to pointers to select two candidate nums[left] and nums[right]

Code O(n)

``````class Solution(object):
def sortTransformedArray(self, nums, a, b, c):
"""
:type nums: List[int]
:type a: int
:type b: int
:type c: int
:rtype: List[int]
"""
def qua(x, a, b, c):
return a * x ** 2 + b * x  + c

n = len(nums)
left , right = 0, n - 1
ans = []
while left<= right:
left_val = qua(nums[left], a ,b ,c)
right_val = qua(nums[right], a ,b ,c)
if a >= 0: # a == 0: put larger at the end or smaller in the front both would be ok
if left_val <= right_val: # a > 0 find larger value garanteed larger than any number in the list; put at the end
ans =[right_val]  + ans
right -= 1
else:
ans = [left_val] + ans
left += 1
else:
if left_val <= right_val: # a > 0 find smaller value garanteed smaller than any number in the list; put in the front
ans.append(left_val)
left += 1
else:
ans.append(right_val)
right -= 1

return ans
``````

Java

``````class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
if(nums == null || nums.length == 0) return null;
int n = nums.length;
int i = 0, j = n - 1;
int [] ans = new int [n];
int k = (a >= 0) ?n - 1 : 0;
while(i <= j){
int left = qua(nums[i], a, b, c);
int right = qua(nums[j], a, b, c);
if(a >= 0){
// current larger would be larger for the rest ;
ans[k--] = (left >= right)? qua(nums[i++], a, b, c): qua(nums[j--], a, b, c); // a == 0 both conditions would apply
}
else{
// current smaller would be smaller for the rest ;
ans[k++] = (left <= right)? qua(nums[i++], a, b, c): qua(nums[j--], a, b, c);
}
}

return ans;
}
private int qua (int x, int a, int b, int c){
return a * x * x + b *x + c;
}
}
``````