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+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]
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.Complexity: O(n) time and constant extra space
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
Last modified 4yr ago