# 360. Sort Transformed Array

## Description

Given a sorted integer array nums and three integers a, b and c, apply a quadratic function of the form f(x) = ax2 + bx + c to each element nums[i] in the array, and return the array in a sorted order.

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]


Example 2:

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


Constraints:

• 1 <= nums.length <= 200
• -100 <= nums[i], a, b, c <= 100
• nums is sorted in ascending order.

Follow up: Could you solve it in O(n) time?

## Solutions

Similar to 302-Smallest-Rectangle-Enclosing-Black-Pixels/ using Callable/Caller to simplify code with two branches.

The provided Python code is a solution for transforming and sorting an array based on the quadratic equation f(x) = ax^2 + bx + c, where a, b, and c are given integers, and x represents elements of the input array nums. The solution uses a two-pointer approach to efficiently sort the transformed values in either ascending or descending order, depending on the coefficient a.

### Code Breakdown

1. Initialization:
• n stores the length of the input array nums.
• result is initialized to store the sorted transformed array, initially filled with zeros.
• Two pointers i and j are initialized to the start and end of the array, respectively.
• idx determines the position in the result array where the next value will be placed. Its initial value depends on the sign of a:
• If a <= 0, the parabola opens upwards (concave up), and the smallest values are on the edges; thus, idx starts at 0.
• If a > 0, the parabola opens downwards (concave down), and the largest values are on the edges; thus, idx starts at n - 1.
2. Lambda Function caller:
• This lambda function is defined to decide whether to take the left_val or right_val based on the sign of a. It facilitates the comparison condition for populating the result array with the correct order of transformed values.
3. Main Loop:
• The loop runs as long as i <= j, indicating that there are elements left to be considered.
• left_val and right_val are calculated by applying the given quadratic formula to nums[i] and nums[j], respectively.
• The caller function is used to compare left_val and right_val. Based on this comparison and the sign of a, either left_val or right_val is placed in the current idx position of the result array.
• The pointer i is incremented if left_val is chosen, and j is decremented if right_val is chosen, moving the pointers towards the center of nums.
• idx is adjusted accordingly after each iteration: incremented if a <= 0 (filling result from start to end) and decremented if a > 0 (filling result from end to start).
4. Function calculate:
• A helper method to apply the quadratic transformation to a given value x.
• class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int n = nums.length;
int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
int[] res = new int[n];
while (i <= j) {
int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
if (a < 0) {
if (v1 <= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
++k;
} else {
if (v1 >= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
--k;
}
}
return res;
}

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

• class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
int n = nums.size();
int i = 0, j = n - 1, k = a < 0 ? 0 : n - 1;
vector<int> res(n);
while (i <= j) {
int v1 = f(a, b, c, nums[i]), v2 = f(a, b, c, nums[j]);
if (a < 0) {
if (v1 <= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
++k;
} else {
if (v1 >= v2) {
res[k] = v1;
++i;
} else {
res[k] = v2;
--j;
}
--k;
}
}
return res;
}

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

• class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
n = len(nums)
result = [0] * n
i, j = 0, n - 1
idx = 0 if a <= 0 else n - 1
# This lambda function is then used to determine the comparison condition
#   for assigning values to the result array
caller = lambda x, y: x >= y if a >= 0 else x <= y

while i <= j:
left_val = self.calculate(nums[i], a, b, c)
right_val = self.calculate(nums[j], a, b, c)

if caller(left_val, right_val):
result[idx] = left_val
i += 1
else:
result[idx] = right_val
j -= 1

idx += (1 if a <= 0 else -1)

return result

def calculate(self, x: int, a: int, b: int, c: int) -> int:
return a * x * x + b * x + c

#############

# reverse() will not work: if (a < 0) reverse(ans.begin(), ans.end());
class Solution:
def sortTransformedArray(
self, nums: List[int], a: int, b: int, c: int
) -> List[int]:
def f(x):
return a * x * x + b * x + c

n = len(nums)
i, j, k = 0, n - 1, 0 if a < 0 else n - 1
res = [0] * n
while i <= j:
v1, v2 = f(nums[i]), f(nums[j]) # here duplicated calculation
if a < 0:
if v1 <= v2:
res[k] = v1
i += 1
else:
res[k] = v2
j -= 1
k += 1
else:
if v1 >= v2:
res[k] = v1
i += 1
else:
res[k] = v2
j -= 1
k -= 1
return res


• func sortTransformedArray(nums []int, a int, b int, c int) []int {
n := len(nums)
i, j, k := 0, n-1, 0
if a >= 0 {
k = n - 1
}
res := make([]int, n)
for i <= j {
v1, v2 := f(a, b, c, nums[i]), f(a, b, c, nums[j])
if a < 0 {
if v1 <= v2 {
res[k] = v1
i++
} else {
res[k] = v2
j--
}
k++
} else {
if v1 >= v2 {
res[k] = v1
i++
} else {
res[k] = v2
j--
}
k--
}
}
return res
}

func f(a, b, c, x int) int {
return a*x*x + b*x + c
}