NUHMAN.com

📘 Problem Statement

You are given a sorted array of integers and a quadratic function defined as:

r

f(x) = ax² + bx + c

You need to apply this function to each element of the array and return the resulting values in sorted order.

🧠 Key Insight

Since the input array is sorted and the quadratic function forms a parabola, we can take advantage of the shape:

• If a > 0: Parabola opens upward ⇒ Min value in the middle, max values on ends.
• If a < 0: Parabola opens downward ⇒ Max value in the middle, min values on ends.

Thus, we can use a two-pointer approach, applying the function to both ends and filling the output array accordingly.

🐍 Python Code

python

from typing import List

class Solution:
    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
        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

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

            if a >= 0:
                if left_val > right_val:
                    result[index] = left_val
                    left += 1
                else:
                    result[index] = right_val
                    right -= 1
                index -= 1
            else:
                if left_val < right_val:
                    result[index] = left_val
                    left += 1
                else:
                    result[index] = right_val
                    right -= 1
                index += 1

        return result

🔍 Step-by-Step Explanation

1. Helper Function to Transform Value

python

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

2. Two-Pointer Initialization

python

left, right = 0, len(nums) - 1

3. Decide Filling Direction

• If a >= 0: fill from end to start (since largest values are on the edges).
• If a < 0: fill from start to end (since smallest values are on the edges).

4. Process Elements with Two Pointers

• Compare transformed values from both ends.
• Insert larger/smaller one based on a into result.

💡 Example

python

Input: nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5
Output: [3, 9, 15, 33]

Explanation:
f(x) = x^2 + 3x + 5
f(-4) = 33, f(-2) = 7, f(2) = 15, f(4) = 33
Sorted: [3, 9, 15, 33]

⏱️ Time & Space Complexity

OperationComplexityTimeO(n)SpaceO(n)

🧵 Final Thoughts

This problem is a great mix of math and algorithm design:

• Recognizing the shape of a quadratic function helps optimize the solution.
• The two-pointer approach avoids naive O(n log n) sorting after transformation.