My easy to understand Java AC solution using Two pointers


  • 14
    T

    The idea is simple:
    For a parabola,
    if a >= 0, the min value is at its vertex. So our our sorting should goes from two end points towards the vertex, high to low.
    if a < 0, the max value is at its vertex. So our sort goes the opposite way.

    public class Solution {
        public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
            int[] res = new int[nums.length];
            int start = 0;
            int end = nums.length - 1;
            int i = a >= 0 ? nums.length - 1 : 0;
            while(start <= end) {
                int startNum = getNum(nums[start], a, b, c);
                int endNum = getNum(nums[end], a, b, c);
                if(a >= 0) {
                    if(startNum >= endNum) {
                        res[i--] = startNum;
                        start++;
                    }
                    else{
                        res[i--] = endNum;
                        end--;
                    }
                }
                else{
                    if(startNum <= endNum) {
                        res[i++] = startNum;
                        start++;
                    }
                    else{
                        res[i++] = endNum;
                        end--;
                    }
                }
            }
            return res;
        }
        public int getNum(int x, int a, int b, int c) {
            return a * x * x + b * x + c;
        }
    }
    

  • 1
    M

    Nice solution!


  • 1

    For sure, I forgot the high school math.


  • 0

    I think the statement is a little bit misleading here, since you don't know whether the center is inside the range or not. It only guarantees that the maximum value appears on either side.


  • 0
    L

    I dont understand this line

    int i = a >= 0 ? nums.length - 1 : 0

    I had an idea to find the vertex (minimum/maximum) and then sort till that vertex in ascending or descending depending on a>=0 or a<0. But your solution works well. Can you explain how this line?


  • 1
    D

    Why are you sooooo smart !!


Log in to reply
 

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