# 2ms Java O(n) solution using simple Math and two pointers

1. Find the extremum point
2. scan the array to left and right using two pointers starting from extremum point
``````public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
if(nums == null || nums.length == 0){
return new int[0];
}
int[] res = new int[nums.length];
if(a == 0){
for(int i = 0; i < nums.length; ++i){
int index = b < 0 ? nums.length - i - 1 : i;
res[index] = nums[i] * b + c;
}
return res;
}
double midVal = -(b / (2.0 * a)); //extremum
int midIndex = binarySearch(nums, midVal); //Find extremum's index
int delta = a > 0 ? 1 : -1; //Two cases, a > 0 or a < 0
int index = a > 0 ? 0 : nums.length - 1;

int left = midIndex - 1;
int right = midIndex;
while(left >= 0 || right < nums.length){
double disLeft = left < 0 ? Double.MAX_VALUE : midVal - nums[left]; //Handle boundary case
double disRight = right >= nums.length ? Double.MAX_VALUE : nums[right] - midVal;
if(disLeft < disRight){
res[index] = transfer(nums[left], a, b, c);
--left;
}else{
res[index] = transfer(nums[right], a, b, c);
++right;
}
index += delta;
}
return res;
}

private int transfer(int num, int a, int b, int c){
return a * num * num + b * num + c;
}

private int binarySearch(int[] nums, double midVal){
int low = 0;
int high = nums.length;
while(low < high){
int mid = low + (high - low) / 2;
if(nums[mid] == midVal){
return mid;
}else if(nums[mid] > midVal){
high = mid;
}else{
low = mid + 1;
}
}
return low;
}``````

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