Problem Description

You are given a sorted integer array nums and three integer coefficients a, b, and c. Your task is to apply a quadratic function f(x) = ax² + bx + c to each element in the array and return the resulting values in sorted order.

The challenge lies in efficiently sorting the transformed values. Since the input array is already sorted, and we're applying a quadratic function, the solution leverages the properties of parabolas:

• When a > 0, the parabola opens upward (U-shaped), meaning the maximum values are at the ends of the sorted input array
• When a < 0, the parabola opens downward (∩-shaped), meaning the minimum values are at the ends of the sorted input array
• When a = 0, the function becomes linear f(x) = bx + c

The solution uses a two-pointer approach, starting from both ends of the input array. It compares the transformed values at both pointers and fills the result array:

• If a >= 0, we fill from the end of the result array backwards (since larger values are at the extremes)
• If a < 0, we fill from the beginning of the result array forwards (since smaller values are at the extremes)

For example, if nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5:

• Transform each element: f(-4) = 9, f(-2) = 3, f(2) = 15, f(4) = 33
• Return the sorted result: [3, 9, 15, 33]

Intuition

The key insight comes from understanding the shape of quadratic functions. When we apply f(x) = ax² + bx + c to a sorted array, we need to recognize that a quadratic function forms a parabola.

Let's think about what happens to our sorted values after transformation:

1. For positive a (upward parabola): The function has a minimum point (vertex). Since our input is sorted, the transformed values will be highest at the extremes (leftmost and rightmost elements) and lowest somewhere in the middle. Imagine a U-shape - the further from the vertex, the larger the value.

2. For negative a (downward parabola): The function has a maximum point (vertex). The transformed values will be lowest at the extremes and highest somewhere in the middle. Picture an inverted U-shape.

3. For a = 0: The function becomes linear (f(x) = bx + c), which preserves the relative ordering if b > 0 or reverses it if b < 0.

Since we know the extreme values (either maximum or minimum) are at the ends of our sorted input array, we can use a two-pointer technique. We don't need to transform all values and then sort them - that would take O(n log n) time. Instead, we can build our sorted result in O(n) time by:

• Comparing transformed values from both ends
• Taking the larger one if we're building from largest to smallest (a >= 0)
• Taking the smaller one if we're building from smallest to largest (a < 0)
• Moving the corresponding pointer inward

This works because once we've taken an extreme value, the next extreme value must come from either the same end (moving one step inward) or the opposite end. We're essentially "peeling off" values from the outside in, maintaining sorted order based on the parabola's properties.

Solution Approach

The implementation uses a two-pointer technique combined with understanding of parabola properties:

Step 1: Define the transformation function

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

Step 2: Initialize pointers and result array

• Set two pointers: i = 0 (left) and j = n - 1 (right)
• Create result array of size n
• Initialize position k where we'll place values:
  • If a < 0: Start from beginning (k = 0) since we'll place smaller values first
  • If a >= 0: Start from end (k = n - 1) since we'll place larger values first

Step 3: Process elements using two pointers While i <= j:

1. Calculate transformed values: v1 = f(nums[i]) and v2 = f(nums[j])

2. When a < 0 (downward parabola):

   • The minimum values are at the extremes
   • Compare v1 and v2, take the smaller one
   • Place it at position k and increment k (building array from start)
   • Move the corresponding pointer inward

3. When a >= 0 (upward parabola or linear):

   • The maximum values are at the extremes
   • Compare v1 and v2, take the larger one
   • Place it at position k and decrement k (building array from end)
   • Move the corresponding pointer inward

Algorithm walkthrough with example:

• Input: nums = [-2, 0, 2], a = 1, b = 0, c = 0 (function: f(x) = x²)
• Initial: i = 0, j = 2, k = 2 (since a > 0)
• Iteration 1: f(-2) = 4, f(2) = 4, take either (both equal), place 4 at index 2
• Iteration 2: Compare remaining values, place 4 at index 1
• Iteration 3: f(0) = 0, place 0 at index 0
• Result: [0, 4, 4]

Time Complexity: O(n) - single pass through the array Space Complexity: O(n) - for the result array (or O(1) if we don't count the output)

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input: nums = [-3, -1, 2, 3], a = -1, b = 2, c = 1
Function: f(x) = -x² + 2x + 1

Since a = -1 < 0, we have a downward parabola (∩-shaped), meaning minimum values are at the extremes.

Step 1: Initialize

• Two pointers: i = 0 (pointing to -3), j = 3 (pointing to 3)
• Result array: [_, _, _, _]
• Since a < 0, we fill from the beginning: k = 0

Step 2: Transform and compare extremes

Iteration 1:

• Left value: f(-3) = -(-3)² + 2(-3) + 1 = -9 - 6 + 1 = -14
• Right value: f(3) = -(3)² + 2(3) + 1 = -9 + 6 + 1 = -2
• Since -14 < -2, place -14 at position k=0
• Move left pointer: i = 1
• Result: [-14, _, _, _], increment k = 1

Iteration 2:

• Left value: f(-1) = -(-1)² + 2(-1) + 1 = -1 - 2 + 1 = -2
• Right value: f(3) = -2 (already calculated)
• Both equal, take either (let's take left)
• Place -2 at position k=1
• Move left pointer: i = 2
• Result: [-14, -2, _, _], increment k = 2

Iteration 3:

• Left value: f(2) = -(2)² + 2(2) + 1 = -4 + 4 + 1 = 1
• Right value: f(3) = -2
• Since -2 < 1, place -2 at position k=2
• Move right pointer: j = 2
• Result: [-14, -2, -2, _], increment k = 3

Iteration 4:

• Only one element left: i = j = 2
• f(2) = 1
• Place 1 at position k=3
• Result: [-14, -2, -2, 1]

Final Output: [-14, -2, -2, 1] (sorted in ascending order)

The algorithm efficiently produces the sorted result in O(n) time by leveraging the parabola's property that extreme values (minimums for downward parabola) are at the ends of the sorted input array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a two-pointer approach with pointers i and j starting from opposite ends of the input array. In each iteration of the while loop, exactly one pointer moves (either i increments or j decrements). The loop continues while i <= j, meaning each element in the array is visited exactly once. The function f(x) performs a constant time calculation (O(1)). Therefore, the overall time complexity is O(n), where n is the length of the input array.

Space Complexity: O(n)

The algorithm creates a result array res of size n to store the transformed and sorted values. This is the only additional space used that scales with the input size. The other variables (i, j, k, v1, v2) use constant space O(1). Since we need to return a new sorted array and cannot sort in-place due to the transformation, the O(n) space for the result array is necessary. Therefore, the total space complexity is O(n).

Common Pitfalls

1. Incorrect Comparison Logic for Different Parabola Orientations

One of the most common mistakes is mixing up the comparison logic when determining which value to place in the result array. Developers often confuse when to pick the smaller vs. larger value based on the parabola's orientation.

Pitfall Example:

# INCORRECT: Using the same comparison logic for both cases
if left_value <= right_value:
    result[index] = left_value
    left += 1
else:
    result[index] = right_value
    right -= 1
# This doesn't account for different parabola orientations!

Why This Happens:

• When a < 0 (downward parabola), we want to build the sorted array from smallest to largest, so we pick the smaller value from the extremes
• When a >= 0 (upward parabola), we want to build from largest to smallest (filling backwards), so we pick the larger value from the extremes

Solution: Always use opposite comparison logic for the two cases:

if a < 0:
    # Pick SMALLER value for ascending order
    if left_value <= right_value:
        result[index] = left_value
        left += 1
    else:
        result[index] = right_value
        right -= 1
else:
    # Pick LARGER value for descending fill (then reversed)
    if left_value >= right_value:
        result[index] = left_value
        left += 1
    else:
        result[index] = right_value
        right -= 1

2. Forgetting to Handle the Linear Case (a = 0)

Another pitfall is not properly handling when a = 0, which makes the function linear rather than quadratic.

Pitfall Example:

# INCORRECT: Only checking a > 0 and a < 0
if a > 0:
    index = n - 1
elif a < 0:
    index = 0
# Missing: What if a == 0?

Why This Matters: When a = 0, the function becomes f(x) = bx + c. The transformation maintains the monotonic property of the sorted input:

• If b >= 0, the array remains in ascending order
• If b < 0, the array becomes descending

Solution: Group a = 0 with a > 0 case (or handle it separately based on b):

# Correct approach: a >= 0 handles both upward parabola and linear cases
index = 0 if a < 0 else n - 1

3. Index Management Errors

Incorrectly updating the result array index can lead to overwriting values or accessing out-of-bounds indices.

Pitfall Example:

# INCORRECT: Forgetting to update index or updating in wrong direction
while left <= right:
    # ... comparison logic ...
    result[index] = selected_value
    # Forgot to update index!
    # Or updating index++ when should be index--

Solution: Ensure index updates match the filling direction:

if a < 0:
    # Fill forward: increment index
    result[index] = selected_value
    index += 1
else:
    # Fill backward: decrement index
    result[index] = selected_value
    index -= 1

4. Not Recognizing the Two-Pointer Opportunity

A naive approach would be to transform all values first, then sort them, resulting in O(n log n) complexity.

Pitfall Example:

# INEFFICIENT: Transform then sort
def sortTransformedArray(nums, a, b, c):
    result = []
    for x in nums:
        result.append(a * x * x + b * x + c)
    return sorted(result)  # O(n log n) - unnecessary!

Solution: Leverage the parabola properties and sorted input to achieve O(n) complexity using the two-pointer technique as shown in the main solution.