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

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 a Quadratic Transform of a Sorted Array

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.

Hints

1. 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?
2. 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.
3. 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: axx alone can reach 10^12.

Approach

For a >= 0, f is convex (or linear), so on the sorted array its values decrease and then increase: the largest remaining value is always at one of the two ends of the unprocessed window. The reference keeps pointers lo and hi, compares f(nums[lo]) with f(nums[hi]), writes the larger into the output from the back, and moves that pointer inward. For a < 0, f is concave, so the smallest remaining value is always at an end; the reference writes the smaller one into the output from the front instead. Each element is evaluated and placed exactly once, ties between the two ends are harmless because both values end up adjacent, and duplicates are kept because every index is consumed individually. All products use 64-bit integers since |axx| can reach 10^12. Sorting all f values directly is also correct but costs O(n log n).

• Time complexity: O(n)
• Space complexity: O(n) for the output array (O(1) extra besides it)