Sorted Transformed Array — Quadratic Function Application

🧮 Sorted Transformed Array — Quadratic Function Application

Problem Statement
You are given a sorted array of integers (can be positive or negative). You want to apply a function of the form:

to each element \(x\) in the array, and return the resulting array in sorted order.

Input:

• A sorted array nums of integers.
• Coefficients a, b, and c for the quadratic function.

Output:

• A new array, sorted in non-decreasing order, where each element is f(x) applied to each x from nums.

This question appeared in a Google interview and was shared on Glassdoor.

🧠 Thought Process

This problem seems simple — just apply the function — but preserving the sorted order is the tricky part.

Key Observations

• The function \(f(x) = ax^2 + bx + c\) is quadratic, forming a parabola:
  • If \(a > 0\), the parabola opens upwards (U-shaped).
  • If \(a < 0\), it opens downwards (∩-shaped).
• Because of this curvature, applying the function may break the sorted order.

Strategy

• Use a two-pointer approach:
  • The original array is sorted. After transformation, the largest/smallest values might now be at the ends.
  • Compare transformed values at both ends and build the result array from back to front (or front to back), depending on the direction the parabola opens.

💻 Python Implementation

def apply_and_sort(nums, a, b, c):
    def f(x):
        return a * x * x + b * x + c

    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    index = n - 1 if a >= 0 else 0  # direction of filling

    while left <= right:
        left_val = f(nums[left])
        right_val = f(nums[right])

        if a >= 0:
            # Insert larger transformed value at the end
            if left_val > right_val:
                result[index] = left_val
                left += 1
            else:
                result[index] = right_val
                right -= 1
            index -= 1
        else:
            # Insert smaller transformed value at the start
            if left_val < right_val:
                result[index] = left_val
                left += 1
            else:
                result[index] = right_val
                right -= 1
            index += 1

    return result

🧪 Test Cases

nums = [-4, -2, 0, 1, 3]
a, b, c = 1, 3, 5
output = apply_and_sort(nums, a, b, c)
assert output == sorted(output)

nums = [-3, -1, 0, 2, 4]
a, b, c = -1, 0, 0
output = apply_and_sort(nums, a, b, c)
assert output == sorted(output)

nums = [-5, -2, 0, 3, 7]
a, b, c = 0, 2, 1
output = apply_and_sort(nums, a, b, c)
assert output == sorted(output)