Katkat
Back

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

WaymoSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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]