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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.