Sort the values of a quadratic function applied to a sorted array in linear time
Company: LinkedIn
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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`.
Overview: Given an integer array sorted in ascending order and the coefficients of a quadratic function, apply the function to every element and return the results in sorted order in linear time. Tests reasoning about the shape of a parabola, handling of positive, negative and zero leading coefficients, and duplicate values.
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`.
**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. No value, and no intermediate product such as `a * x^2` (at most `10^8` in magnitude), can exceed 2^31-1, so Java and C++ use `int`.
**Example 1**
```text
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**
```text
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`.
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]) = a * nums[i]^2 + b * nums[i] + c lies between -100100100 and 100100100, so all values fit in a 32-bit signed integer (none exceeds 2^31-1)
Examples
Input: ([-4, -2, 2, 4], 1, 3, 5)
Expected Output: [3, 9, 15, 33]
Explanation: Source Example 1: upward parabola (a > 0) on inputs straddling zero; f values 9, 3, 15, 33 in sorted order.
Input: ([-4, -2, 2, 4], -1, 3, 5)
Expected Output: [-23, -5, 1, 7]
Explanation: Source Example 2: downward parabola (a < 0); f values -23, -5, 7, 1 in sorted order, so the smaller end is placed first.
Hints
- The sign of a decides whether the graph of f opens upward or downward; a = 0 turns it into a straight line, or a constant when b = 0 as well.
- nums is already sorted. Think about which elements of a sorted range can give the largest or smallest value of f on that range.
- Every element contributes exactly one value: equal inputs, and different inputs on either side of the turning point that map to the same value, all stay in the output.