Leetcode 360. Sort Transformed Array

Problem Description

In this problem, we are given an array of integers that is already sorted. We are also provided with three more integer values a, b, and c. The problem requires us to apply a quadratic function of the form f(x) = ax^2 + bx + c to each element x in the array. Following the application of this quadratic function, we have to return a new array which is sorted in order. We need to find this sorted transformed array in (O)n time complexity.

Let's walk through an example:

Example: Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5

Now, applying the quadratic function for each element in the array: f(-4) = 1(-4)^2 + 3(-4) + 5 = 33 f(-2) = 1(-2)^2 + 3(-2) + 5 = 9 f(2) = 1(2)^2 + 3(2) + 5 = 15 f(4) = 1(4)^2 + 3(4) + 5 = 29

So, the output is [3,9,15,33]

This problem can be solved using the two-pointer approach. Since the given array is already sorted, we can use two pointers to keep track of the left and right elements in the array.

The parabola for the function f(x) = ax^2 + bx + c is either upward-opening (if a > 0) or downward-opening (if a < 0). If it's upward-opening, the maximum value will occur at the edges (either at the beginning or the end), and if it's downward-opening, the minimum will occur at the edges. Hence, if 'a' is positive we start filling the answer array from the end, otherwise, we start filling it from the start.

For example, applying the quadratic function to the array [-4,-2,2,4] with a=1, b=3, and c=5, f(-4) and f(4) will be larger than f(-2) and f(2), so we put the larger values in the ends of the answer array and the smaller values in the middle.

Python Solution

1
2python
3class Solution:
4    def sortTransformedArray(self, nums, a, b, c):
5        n = len(nums)
6        quad = [(a*x*x + b*x + c) for x in nums]  # apply the quadratic function to each num
7        
8        # Initialize i as the last index if a>0, else as the first index
9        i = n - 1 if a > 0 else 0
10        
11        transformed = [0] * n # output array
12        l, r = 0, n - 1 # two pointers for both ends of the array
13        
14        while l <= r:
15            if a > 0: 
16                # If the parabola opens upwards, we fill the output array from the end
17                if quad[l] > quad[r]:
18                    transformed[i] = quad[l]
19                    l += 1
20                else:
21                    transformed[i] = quad[r]
22                    r -= 1
23                i -= 1
24            else:
25                # If the parabola opens downwards, we fill the output array from the start
26                if quad[l] < quad[r]:
27                    transformed[i] = quad[l]
28                    l += 1
29                else:
30                    transformed[i] = quad[r]
31                    r -= 1
32                i += 1
33                
34        return transformed

This solution creates a new array quad that contains the quadratic transformation of each number in nums. Then it initializes two pointers (l and r) at the beginning and end of the array. If a is positive, it starts filling the output array from the end, taking the larger of the two numbers pointed to by l and r. It then updates the pointers accordingly. If a is negative, it does the opposite, filling the output array from the beginning with the smaller of the two numbers and updating the pointers. It keeps doing this until it has filled the entire output array, which is then returned.## JavaScript (JS) Solution

In JavaScript, we can follow a similar approach using the map and sort functions:

1
2js
3var sortTransformedArray = function(nums, a, b, c) {
4    let n = nums.length;
5    // Apply the quadratic function to each num
6    let quad = nums.map((x) => (a*x*x + b*x + c)).sort((a, b) => a - b);
7
8    // Initialize i as the last index if a>0, else as the first index
9    let i = a > 0 ? n - 1 : 0;
10    
11    let transformed = new Array(n);
12    let l = 0, r = n - 1;  // Two pointers for both ends of the array
13    
14    while (l <= r) {
15        if (a > 0) { 
16            // If the parabola opens upwards, we fill the output array from the end
17            if (quad[l] > quad[r]) {
18                transformed[i] = quad[l];
19                l += 1;
20            } else {
21                transformed[i] = quad[r];
22                r -= 1;
23            }
24            i -= 1;
25        } else {
26            // If the parabola opens downwards, we fill the output array from the start
27            if (quad[l] < quad[r]) {
28                transformed[i] = quad[l];
29                l += 1;
30            } else {
31                transformed[i] = quad[r];
32                r -= 1;
33            }
34            i += 1;
35        }
36    }
37    
38    return transformed;
39};

Java Solution

In Java, we'll need to declare and initialize our variables and arrays beforehand:

1
2java
3public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
4    int n = nums.length;
5    // Apply the quadratic function to each num
6    int[] quad = new int[n];
7    for (int i = 0; i < n; i++) {
8        quad[i] = a*nums[i]*nums[i] + b*nums[i] + c;
9    }
10
11    // Initialize output array and pointers
12    int[] transformed = new int[n];
13    int l = 0, r = n - 1;
14
15    // Initialize i as the last index if a>0, else as the first index
16    int i = a > 0 ? n - 1 : 0;
17
18    while (l <= r) {
19        if (a > 0) { 
20            // If the parabola opens upwards, we fill the output array from the end
21            if (quad[l] > quad[r]) {
22                transformed[i] = quad[l];
23                l++;
24            } else {
25                transformed[i] = quad[r];
26                r--;
27            }
28            i--;
29        } else {
30            // If the parabola opens downwards, we fill the output array from the start
31            if (quad[l] < quad[r]) {
32                transformed[i] = quad[l];
33                l++;
34            } else {
35                transformed[i] = quad[r];
36                r--;
37            }
38            i++;
39        }
40    }
41    
42    return transformed;
43}

Each of these solutions utilizes the two-pointer approach and takes advantage of the sorted nature of the input array to achieve O(n) time complexity.