• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
const int n = nums.size();
const bool upward = a > 0;
vector<int> ans(n);

for (const int num : nums)

int i = upward ? n - 1 : 0;
for (int l = 0, r = n - 1; l <= r;)
if (upward)  // maximum in both ends
else  // minimum in both ends

return ans;
}

private:
// the concavity of f only depends on a's sign
int f(int x, int a, int b, int c) {
return (a * x + b) * x + c;
}
};
``````

## JAVA

``````class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
final int n = nums.length;
final boolean upward = a > 0;
int[] ans = new int[n];

for (int i = 0; i < nums.length; ++i)
quad[i] = f(nums[i], a, b, c);

int i = upward ? n - 1 : 0;
for (int l = 0, r = n - 1; l <= r;)
if (upward) // maximum in both ends
else // minimum in both ends

return ans;
}

// the concavity of f only depends on a's sign
private int f(int x, int a, int b, int c) {
return (a * x + b) * x + c;
}
}
``````

## Python

``````class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
n = len(nums)
upward = a > 0
ans = [0] * n

# the concavity of f only depends on a's sign
def f(x: int, a: int, b: int, c: int) -> int:
return (a * x + b) * x + c

quad = [f(num, a, b, c) for num in nums]

i = n - 1 if upward else 0
l = 0
r = n - 1
while l <= r:
if upward:  # maximum in both ends
l += 1
else: