# 360. Sort Transformed Array

Given a sorted array of integers  nums  and integer values  ab and  c. Apply a quadratic function of the form f( x ) =  ax 2 +  bx  +  c  to each element  x  in the array.

The returned array must be in sorted order.

Expected time complexity: O( n )

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]
``````

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

``````class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
vector<int> res;
priority_queue<int, vector<int>, greater<int>> q;
for (auto d : nums) {
q.push(a * d * d + b * d + c);
}
while (!q.empty()) {
res.push_back(q.top()); q.pop();
}
return res;
}
};
``````

``````class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
int n = nums.size(), i = 0, j = n - 1;
vector<int> res(n);
int idx = a >= 0 ? n - 1 : 0;
while (i <= j) {
if (a >= 0) {
res[idx--] = cal(nums[i], a, b, c) >= cal(nums[j], a, b, c) ? cal(nums[i++], a, b, c) : cal(nums[j--], a, b, c);
} else {
res[idx++] = cal(nums[i], a, b, c) >= cal(nums[j], a, b, c) ? cal(nums[j--], a, b, c) : cal(nums[i++], a, b, c);
}
}
return res;
}
int cal(int x, int a, int b, int c) {
return a * x * x + b * x + c;
}
};
``````

Squares of a Sorted Array

https://leetcode.com/problems/sort-transformed-array/

https://leetcode.com/discuss/108831/java-o-n-incredibly-short-yet-easy-to-understand-ac-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation