Waymo: Sort the Results of Applying a Quadratic Function to a Sorted Array

Quick Overview

Apply the quadratic function a*x*x + b*x + c to every element of a sorted integer array and return the results in sorted order, where a may be negative or zero. Tests reasoning about the parabola's shape and merging values from both ends in linear time.

You are given the three integer coefficients a, b and c of the quadratic function f(x) = a*x*x + b*x + c, and an integer array nums sorted in non-decreasing order. Apply f to every element and return the results sorted in non-decreasing order.

Pay attention to the sign of a: it may be negative, and it may also be zero.

Function Signature

def transform_and_sort(nums: list[int], a: int, b: int, c: int) -> list[int]:

Rules

The output has the same length as nums and contains f(nums[i]) for every index i , including repeated values.
The output is sorted in non-decreasing order.

Constraints

1 <= len(nums) <= 10^5
-10^4 <= nums[i] <= 10^4 , and nums is sorted in non-decreasing order (duplicates allowed).
-10^4 <= a, b, c <= 10^4
Every value of f(nums[i]) has absolute value at most about 1.0001 * 10^12 , which is within 2^53 .

Examples

Example 1

Input: nums = [-3, -1, 0, 2, 5] , a = -1 , b = 2 , c = 1
Output: [-14, -14, -2, 1, 1]
Explanation: f(-3) = -14 , f(-1) = -2 , f(0) = 1 , f(2) = 1 , f(5) = -14 . With a negative a , the largest values come from the middle of the array.

Example 2

Input: nums = [-2, 1, 3, 3] , a = 0 , b = -3 , c = 4
Output: [-5, -5, 1, 10]
Explanation: With a = 0 the function is linear and decreasing, so the order of the inputs is reversed.

Example 3

Input: nums = [-5, -2, 0, 1, 4] , a = 2 , b = 0 , c = -3
Output: [-3, -1, 5, 29, 47]

Sort the Results of Applying a Quadratic Function to a Sorted Array