Java O(N) easy, verbose, explained, picture, with math recap

• Code:

``````class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
if (nums.length == 0 || nums == null)
return new int[0];
int n = nums.length;
int[] res = new int[n];
if (a == 0) {
for (int i = 0; i < n; i++) {
int cur = b >= 0 ? nums[i] : nums[n - 1 - i];
res[i] = b * cur + c;
}
return res;
}
//sort based on distance to pivot
double pivot = (double) -b / (2 * a);
int[] distSorted = new int[n];
int lo = 0, hi = n - 1, end = n - 1;
while (lo <= hi) {
double d1 = pivot - nums[lo], d2 = nums[hi] - pivot;
if (d1 > d2) {
distSorted[end--] = nums[lo++];
} else {
distSorted[end--] = nums[hi--];
}
}
//populate res based on distSorted, and also a
for (int i = 0; i < n; i++) {
int cur = a > 0 ? distSorted[i] : distSorted[n - 1 - i];
res[i] = a * cur * cur + b * cur + c;
}
return res;
}
}
``````

And the picture:

The process consists of two procedures:

1. sort all numbers (`x`s) by their distance to the pivot;
2. populate the result array (`y`s).

The code should be easy to understand with the idea explained by the picture.

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