# 7-line and 9-line concise solutions with explanation

1. a > 0: `y = a*x*x+b*x+c` => y value goes down and goes up

1. a < 0: y value goes up and goes down

A `list` is used for insertion since it may be inserted before or after. For every entry, the right position is computed. This may sound like O(n^2) or O(nlogn). Assuming case 1 without loss of generality, the iterator (location/index finder) initially travels down and eventually travels up due to the property of the function. It consumes at most `O(2n)` for inner and outer loop. For the final step, list data is copied into output.

``````class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
list<int> l;
list<int>::iterator it = l.begin();
for (auto& x: nums) {
int y = a*x*x + b*x + c;
while (it != l.begin() && *it > y) it--;
while (it != l.end() && *it < y) it++;
it = l.insert(it, y);
}
return vector<int>(l.begin(), l.end());
}
};
``````

The first solution is what I came up when doing the question myself. After reading other posts, I just rewrite another way of doing it. The detail explanation can be found in this link.

``````class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
vector<int> res(nums.size()), y;
for (auto &x: nums) y.emplace_back(a*x*x+b*x+c);

int i = 0, j = nums.size()-1, k = a<0? 0: nums.size()-1;
for(; i <= j; k += a<0? 1: -1) {
if (y[i] < y[j] == a < 0) res[k] = y[i++];
else                      res[k] = y[j--];
}
return res;
}
};
``````

• This post is deleted!

• Nice solutions, I particularly like the first one because I hadn't seen that before.

Just one not so nice thing: Both the problem and your own text call the elements "x" and the number of elements "n", but your code then goes against all that and calls the elements "n".

• Thanks for the suggestion! Fix it now.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.