Code Implementation

class Solution:
    def sortTransformedArray(self, 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
        idx = 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[idx] = left_val
                    left += 1
                else:
                    result[idx] = right_val
                    right -= 1
                idx -= 1
            else:
                if left_val < right_val:
                    result[idx] = left_val
                    left += 1
                else:
                    result[idx] = right_val
                    right -= 1
                idx += 1
        return result
      

class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        auto f = [&](int x) { return a * x * x + b * x + c; };
        int n = nums.size();
        vector<int> result(n);
        int left = 0, right = n - 1;
        int idx = a >= 0 ? n - 1 : 0;
        while (left <= right) {
            int leftVal = f(nums[left]);
            int rightVal = f(nums[right]);
            if (a >= 0) {
                if (leftVal > rightVal) {
                    result[idx--] = leftVal;
                    left++;
                } else {
                    result[idx--] = rightVal;
                    right--;
                }
            } else {
                if (leftVal < rightVal) {
                    result[idx++] = leftVal;
                    left++;
                } else {
                    result[idx++] = rightVal;
                    right--;
                }
            }
        }
        return result;
    }
};
      

class Solution {
    private int f(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }

    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int idx = a >= 0 ? n - 1 : 0;

        while (left <= right) {
            int leftVal = f(nums[left], a, b, c);
            int rightVal = f(nums[right], a, b, c);
            if (a >= 0) {
                if (leftVal > rightVal) {
                    result[idx--] = leftVal;
                    left++;
                } else {
                    result[idx--] = rightVal;
                    right--;
                }
            } else {
                if (leftVal < rightVal) {
                    result[idx++] = leftVal;
                    left++;
                } else {
                    result[idx++] = rightVal;
                    right--;
                }
            }
        }
        return result;
    }
}
      

var sortTransformedArray = function(nums, a, b, c) {
    function f(x) {
        return a * x * x + b * x + c;
    }
    let n = nums.length;
    let result = new Array(n);
    let left = 0, right = n - 1;
    let idx = a >= 0 ? n - 1 : 0;

    while (left <= right) {
        let leftVal = f(nums[left]);
        let rightVal = f(nums[right]);
        if (a >= 0) {
            if (leftVal > rightVal) {
                result[idx--] = leftVal;
                left++;
            } else {
                result[idx--] = rightVal;
                right--;
            }
        } else {
            if (leftVal < rightVal) {
                result[idx++] = leftVal;
                left++;
            } else {
                result[idx++] = rightVal;
                right--;
            }
        }
    }
    return result;
};
      

Problem Description

You are given a sorted array of integers nums and three integer coefficients a, b, and c. You need to apply the quadratic function f(x) = a * x^2 + b * x + c to each element x in nums, and then return the resulting array sorted in ascending order.

• The input array nums is sorted in non-decreasing order.
• You must apply the function to each element exactly once.
• Return a new array, not a modification of the original.
• The result must be in ascending order, regardless of the function's shape.

Thought Process

At first glance, this problem looks like a straightforward mapping: just apply the function to each element and sort the result. However, since nums is already sorted, and because the quadratic function can either open upwards (a > 0) or downwards (a < 0), we can exploit the structure to optimize the solution.

If we were to simply map and sort, it would work but would not be efficient. Instead, we can notice that:

• If a > 0, the function is convex (U-shaped), so the largest values are at the ends of nums.
• If a < 0, the function is concave (∩-shaped), so the smallest values are at the ends.
• If a == 0, the function is linear, and the order depends on b.

This means we can use a two-pointer approach, similar to merging two sorted arrays, to construct the result efficiently.

Solution Approach

• Step 1: Define the quadratic function f(x) = a * x^2 + b * x + c.
• Step 2: Use two pointers, left at the start and right at the end of nums.
• Step 3: Depending on the value of a:
  • If a >= 0: The largest transformed values are at the ends. Fill the result array from the end to the start, comparing f(nums[left]) and f(nums[right]) each time and placing the larger at the end.
  • If a < 0: The smallest transformed values are at the ends. Fill the result array from the start to the end, placing the smaller of f(nums[left]) and f(nums[right]) at the front.
• Step 4: Move the pointers inward after placing a value, repeating until all elements are processed.
• Step 5: Return the filled and sorted result array.

This approach ensures we only traverse the array once, achieving linear time complexity.

Example Walkthrough

Let's use nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5.

• Apply f(x) = x^2 + 3x + 5 to each element:
• • f(-4) = 16 - 12 + 5 = 9
  • f(-2) = 4 - 6 + 5 = 3
  • f(2) = 4 + 6 + 5 = 15
  • f(4) = 16 + 12 + 5 = 33
• The transformed array is [9, 3, 15, 33]. But this is not sorted.
• Using the two-pointer approach:
  • Compare f(-4)=9 and f(4)=33. Place 33 at the end.
  • Compare f(-4)=9 and f(2)=15. Place 15 next.
  • Compare f(-4)=9 and f(-2)=3. Place 9 next.
  • Only f(-2)=3 remains. Place it at the start.

  The result is [3, 9, 15, 33], which is sorted.

Time and Space Complexity

• Brute-force approach:
  • Apply the function to each element: O(n).
  • Sort the result: O(n log n).
  • Total: O(n log n)
• Optimized two-pointer approach:
  • Each element is processed exactly once: O(n).
  • Result is filled in-place, so extra space is O(n) for the output.
  • Total: O(n) time, O(n) space.

The optimized method is significantly faster for large input sizes.

Summary

By leveraging the properties of the quadratic function and the sorted nature of the input array, we avoid unnecessary sorting and achieve a linear time solution. The two-pointer strategy lets us build the result from both ends, ensuring correct order and efficiency. This approach demonstrates the power of combining mathematical insights with algorithmic techniques for elegant and optimal solutions.