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+cto 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]
Complexity: O(n) time and constant extra space
import operatorclassSolution:defsortTransformedArray(self,nums,a,b,c):""" :type nums: List[int] :type a: int :type b: int :type c: int :rtype: List[int] """defquad(x):return (a *pow(x, 2)) + (b * x) + c solution = [0] *len(nums)defiter_forward_or_rev(start,add,cmp): left =0 right =len(nums)-1while left <= right:ifcmp(quad(nums[left]), quad(nums[right])): solution[start]=quad(nums[left]) left +=1else: 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 smallestif a >0:iter_forward_or_rev(len(nums) -1, -1, operator.gt)else:iter_forward_or_rev(0, 1, operator.lt)return solution
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 ora=0 and b<0 , both these cases can be reduced to following the same logic following when a <= 0.