Katkat
Back

Return sorted values after quadratic transform

Two SigmaData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently transform elements in a sorted array using a quadratic function and merge them back into a single sorted array in linear time.

Problem Statement

Given a sorted array of integers nums (which may include negative numbers) and three coefficients a, b, and c, return an array containing the squares of each element transformed by the quadratic function f(x) = ax^2 + bx + c, sorted in ascending order.

Function Signature

def sorted_quadratic_transform(nums: List[int], a: int, b: int, c: int) -> List[int]:

Constraints

  • n (length of nums) is between 1 and 10^5.
  • The values in nums are between -10^4 and 10^4.
  • a, b, and c are integers between -100 and 100.
  • You should aim for a time complexity of O(n).

Examples

Example 1: Input: nums = [-3, -1, 2, 4], a = 1, b = 0, c = 0 Output: [1, 4, 9, 16] Explanation: The transformed values are [9, 1, 4, 16]. Sorting these gives [1, 4, 9, 16].

Example 2: Input: nums = [-3, -2, 1, 4], a = -1, b = 2, c = 1 Output: [-14, -2, 2, 2] Explanation: The transformed values are [-14, -7, 2, -7]. Sorting these gives [-14, -7, -7, 2].

Edge Cases

  • Array containing all negative numbers.
  • Array containing all positive numbers.
  • The vertex of the parabola x = -b / (2a) falling inside or outside the range of nums.

Hints

Hint 1

Note that for a quadratic function, the values are monotonic on either side of the vertex (-b / 2a).

Hint 2

If a > 0, the function is U-shaped; if a < 0, it is inverted U-shaped; if a = 0, it is monotonic.

Hint 3

Since the input is already sorted, you can identify the two ends of the array that will produce the largest (or smallest) values and use a two-pointer approach similar to merging sorted lists.

Follow-up questions

  • How would your approach change if the input array was not sorted?
  • What if the function was a higher-degree polynomial, like a cubic function? Would the two-pointer approach still work?
  • How would you handle potential integer overflows if the coefficients or input values were significantly larger?