Sort the Results of Applying a Quadratic Function to a Sorted Array
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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]`
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 an integer array `nums` sorted in non-decreasing order, and the three integer coefficients `a`, `b` and `c` of the quadratic function `f(x) = a*x*x + b*x + c`. Apply `f` to every element of `nums` and return the results sorted in non-decreasing order.
Watch the sign of `a`: it may be positive, negative, or zero (in which case `f` is linear, or even constant when `b` is also zero).
Implement `transform_and_sort(nums, a, b, c)`:
- The returned list has the same length as `nums` and contains `f(nums[i])` for every index `i`, so repeated input values and distinct inputs that map to the same output each keep their own copy.
- The returned list is sorted in non-decreasing order. Because it is the sorted multiset of `f(nums[i])`, there is exactly one correct answer for every input.
### 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. Both copies of `3` produce `-5`.
### Example 3
- Input: `nums = [-5, -2, 0, 1, 4]`, `a = 2`, `b = 0`, `c = -3`
- Output: `[-3, -1, 5, 29, 47]`
### 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 `f(nums[i])` has absolute value at most `10^12 + 10^8 + 10^4` (about `1.0001 * 10^12`). This exceeds the 32-bit signed range (`2^31 - 1`), so compute and return the values as 64-bit integers (`long` in Java, `long long` in C++); it stays within `2^53`, so JavaScript numbers represent every value exactly.
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 (a may be negative or zero)
- |f(nums[i])| <= 10^12 + 10^8 + 10^4 (about 1.0001 * 10^12): beyond 32-bit, so use 64-bit integers (long in Java, long long in C++); within 2^53, so exact in JavaScript
Examples
Input: ([-3, -1, 0, 2, 5], -1, 2, 1)
Expected Output: [-14, -14, -2, 1, 1]
Explanation: Worked example 1: a < 0, the vertex is inside the array, and f(-3) = f(5) = -14 tie at the low end.
Input: ([-2, 1, 3, 3], 0, -3, 4)
Expected Output: [-5, -5, 1, 10]
Explanation: Worked example 2: a = 0 with b < 0 is linear and decreasing, so the order reverses; the duplicate 3 keeps both copies.
Hints
- A parabola is monotone on each side of its vertex. In a sorted array, where must the largest f value sit when a > 0, and where must the smallest sit when a < 0?
- Keep one pointer at each end of nums. Each step, compare f at the two ends and place the winner at the correct end of the output, then move that pointer inward.
- A linear function (a = 0) is monotone everywhere, so it fits the same end-comparison as the a > 0 case. Compute f with 64-bit arithmetic: a*x*x alone can reach 10^12.