Sort the values of a quadratic function applied to a sorted array in linear time

You are given an integer array nums sorted in non-decreasing order and three integers a, b and c that define the function f(x) = a * x^2 + b * x + c. Apply f to every element of nums and return the resulting values sorted in non-decreasing order. The interviewer asked for a solution that runs in time linear in the length of nums.

Function Signature

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

Rules

• The output contains exactly one value for each element of nums. Repeated values are kept: equal inputs, or different inputs that map to the same value, each contribute their own copy.
• Return the values in non-decreasing order.
• a may be positive, negative or zero. When a = 0 the function is linear, and when a = 0 and b = 0 it is constant.

Constraints

• 1 <= len(nums) <= 10^5
• -1000 <= nums[i] <= 1000, and nums is sorted in non-decreasing order; it may contain duplicates
• -100 <= a, b, c <= 100
• every value f(nums[i]) lies between -100100100 and 100100100, so all values fit in a 32-bit signed integer

Examples

Example 1

Input: nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5
Output: [3, 9, 15, 33]

f(-4) = 9, f(-2) = 3, f(2) = 15 and f(4) = 33, which in sorted order are [3, 9, 15, 33].

Example 2

Input: nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5
Output: [-23, -5, 1, 7]

f(-4) = -23, f(-2) = -5, f(2) = 7 and f(4) = 1.

Example 3

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

f(-1) = 3, f(0) = 1 for each of the two zeros, and f(3) = -5.