Sort Transformed Array

We need to understand the shape of the quadratic function (f(x) = ax^2 + bx + c). Depending on the value of (a), the parabola could either open upwards (when (a > 0)) or downwards (when (a < 0)).

  1. If (a > 0), the smallest values of (f(x)) will be at the two ends of the sorted array, and the largest value will be in the middle.
  2. If (a < 0), the largest values of (f(x)) will be at the two ends of the sorted array, and the smallest value will be in the middle.
  3. If (a = 0), the function is linear and the transformation depends on the sign of (b).

Given the sorted order of nums, we can make use of two pointers (one at the start and the other at the end) to pick the next largest or smallest value.

Here’s the solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:

        # Define the quadratic function
        def f(x):
            return a*x*x + b*x + c

        n = len(nums)
        result = [0] * n

        # Two pointers
        left, right = 0, n - 1

        # If a > 0, fill result from end. Else, fill from start
        index = n - 1 if a > 0 else 0

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

            # For a > 0, choose the largest value
            if a > 0:
                if left_val > right_val:
                    result[index] = left_val
                    left += 1
                else:
                    result[index] = right_val
                    right -= 1
                index -= 1
            # For a <= 0, choose the smallest value
            else:
                if left_val < right_val:
                    result[index] = left_val
                    left += 1
                else:
                    result[index] = right_val
                    right -= 1
                index += 1

        return result

The function f is used to calculate the value of the quadratic function for any (x). Using two pointers, left and right, we then fill in the result array in the desired order depending on the value of (a).