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;
    }
}