Sort Transformed Array

XXX. Sort Transformed Array

Math

Two Pointers

Problem Statement:

Given a sorted array of integers nums and three integers a, b, and c, apply a quadratic transformation to each element of the array: f(x) = ax² + bx + c. Return the transformed array sorted in ascending order.

Algorithm:

1. Initialize two pointers, i at the start of the array and j at the end.
2. Use a helper function to calculate the quadratic transformation for a given x.
3. Depending on the sign of a:
   • If a ≥ 0, the transformed values at the two ends are largest, so fill the result array from the end.
   • If a < 0, the transformed values at the two ends are smallest, so fill the result array from the start.
4. Iterate until the two pointers meet, comparing the transformed values at the two ends and placing the larger/smaller value accordingly.

Complexity:

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n) for the output array.

Java Implementation:

class Solution {
    // If a > 0, the largest number must be at the two ends of the original array.
    // If a < 0, the smallest number must be at the two ends of the original array.
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length, i = 0, j = n - 1;
        int[] sorted = new int[n];
        int index = a >= 0 ? n - 1 : 0; // Determine where to start filling

        while (i <= j)
            if (a >= 0)
                sorted[index--] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[i++], a, b, c) : quad(nums[j--], a, b, c);
            else
                sorted[index++] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[j--], a, b, c) : quad(nums[i++], a, b, c);

        return sorted;
    }

    // Helper function to calculate the quadratic transformation
    private int quad(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}
                

Python Implementation:

def sort_transformed_array(nums, a, b, c):
    def quad(x):
        return a * x * x + b * x + c

    n = len(nums)
    sorted_arr = [0] * n
    i, j = 0, n - 1
    index = n - 1 if a >= 0 else 0

    while i <= j:
        if a >= 0:
            if quad(nums[i]) >= quad(nums[j]):
                sorted_arr[index] = quad(nums[i])
                i += 1
            else:
                sorted_arr[index] = quad(nums[j])
                j -= 1
            index -= 1
        else:
            if quad(nums[i]) >= quad(nums[j]):
                sorted_arr[index] = quad(nums[j])
                j -= 1
            else:
                sorted_arr[index] = quad(nums[i])
                i += 1
            index += 1

    return sorted_arr
                

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    vector sortTransformedArray(vector& nums, int a, int b, int c) {
        auto quad = [&](int x) { return a * x * x + b * x + c; };

        int n = nums.size();
        vector sorted(n);
        int i = 0, j = n - 1;
        int index = a >= 0 ? n - 1 : 0;

        while (i <= j) {
            if (a >= 0)
                sorted[index--] = quad(nums[i]) >= quad(nums[j]) ? quad(nums[i++]) : quad(nums[j--]);
            else
                sorted[index++] = quad(nums[i]) >= quad(nums[j]) ? quad(nums[j--]) : quad(nums[i++]);
        }

        return sorted;
    }
};