Practice/Meta/Leetcode 360. Sort Transformed Array

Leetcode 360. Sort Transformed Array

CodingOptional

Problem

You are given a sorted integer array nums and the coefficients of a quadratic function f(x) = ax² + bx + c. Your task is to apply this function to every element in the array and return a new array containing all the transformed values in sorted order.

The challenge is to achieve this efficiently by leveraging the properties of quadratic functions rather than simply transforming and sorting.

Requirements

1. Transform each element x in nums using the formula f(x) = ax² + bx + c
2. Return the transformed values in non-decreasing sorted order
3. Optimize your solution to run in O(n) time complexity
4. Use the mathematical properties of parabolas to avoid explicit sorting

Constraints

• 1 ≤ nums.length ≤ 5000
• -100 ≤ nums[i] ≤ 100
• nums is sorted in non-decreasing order
• -100 ≤ a, b, c ≤ 100
• Target time complexity: O(n)
• Target space complexity: O(n) for the output array

Examples

Example 1:

Input: nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5 Output: [3, 9, 15, 33] Explanation: f(-4) = 1·16 + 3·(-4) + 5 = 16 - 12 + 5 = 9 f(-2) = 1·4 + 3·(-2) + 5 = 4 - 6 + 5 = 3 f(2) = 1·4 + 3·2 + 5 = 4 + 6 + 5 = 15 f(4) = 1·16 + 3·4 + 5 = 16 + 12 + 5 = 33 Sorted: [3, 9, 15, 33]

Example 2:

Input: nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5 Output: [-7, -5, 3, 7] Explanation: f(-4) = -16 + 3·(-4) + 5 = -16 - 12 + 5 = -7 f(-2) = -4 + 3·(-2) + 5 = -4 - 6 + 5 = -5 f(2) = -4 + 3·2 + 5 = -4 + 6 + 5 = 7 f(4) = -16 + 3·4 + 5 = -16 + 12 + 5 = 3 Sorted: [-7, -5, 3, 7]

Example 3:

Input: nums = [-2, -1, 0, 1, 2], a = 0, b = 1, c = 0 Output: [-2, -1, 0, 1, 2] Explanation: When a = 0, f(x) = x, so the array remains unchanged.