Java O(n) incredibly short yet easy to understand AC solution


  • 109

    the problem seems to have many cases a>0, a=0,a<0, (when a=0, b>0, b<0). However, they can be combined into just 2 cases: a>0 or a<0

    1.a>0, two ends in original array are bigger than center if you learned middle school math before.

    2.a<0, center is bigger than two ends.

    so use two pointers i, j and do a merge-sort like process. depending on sign of a, you may want to start from the beginning or end of the transformed array. For a==0 case, it does not matter what b's sign is.
    The function is monotonically increasing or decreasing. you can start with either beginning or end.

    public class Solution {
        public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
            int n = nums.length;
            int[] sorted = new int[n];
            int i = 0, j = n - 1;
            int index = a >= 0 ? n - 1 : 0;
            while (i <= j) {
                if (a >= 0) {
                    sorted[index--] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[i++], a, b, c) : quad(nums[j--], a, b, c);
                } else {
                    sorted[index++] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[j--], a, b, c) : quad(nums[i++], a, b, c);
                }
            }
            return sorted;
        }
        
        private int quad(int x, int a, int b, int c) {
            return a * x * x + b * x + c;
        }
    }

  • 0
    S

    Nice idea by using two pointers to construct the sorted array.


  • 0
    X
    This post is deleted!

  • 0
    S

    How does it deal when the center is not at the left side?


  • 0

    center is normally not at left end...


  • 7
    H

    Great idea.

    I think the key to undersatnd this algorithm is :

    If a > 0; the smallest number must be at two ends of orgin array;

    If a < 0; the largest number must be at two ends of orgin array;


  • 1
    D

    Though as simple as the solution is already, we can do less computation if a = 0 and b >= 0 (return original array) and also if a = 0 and b < 0 (return reversed array).


  • 0
    A
    This post is deleted!

  • 1
    C

    said in Java O(n) incredibly short yet easy to understand AC solution:

    1.a>0, two ends in original array are bigger than center if you learned middle school math before.
    2.a<0, center is bigger than two ends.

    Appreciate it if anyone could help me understand this:

    1.a>0, two ends in original array are bigger than center if you learned middle school math before.
    2.a<0, center is bigger than two ends.

    How is this true? For example, if the array is [1,2,3,4,5,6], f(x) = x^2+4x+4, f(1) is obviously less than f(4). Did I misunderstand anything here? Thank you guys!


  • 5
    D

    @codingcoconut The first derivative of the equation u provided is 2x + 4 and it equals to 0 when x = -2. Since a = 1 that means the parabola opens upward and x = -2 is the coordinate of the bottom point and also the mid point. Anything on the left or right of it has a greater y-value. Thus, f(1) and f(4), which both are on the right side of f(2), have greater value than f(2). If we use two pointers, one points at the start of the array and one points at the end of it, we will increment or decrement one of the pointers depending which of them has smaller horizontal distance (x-coordinate difference) to the mid point (x = -2 in this case). Since we want descending orders, we will place the smaller one in the array first. Not sure why you are comparing f(1) and f(4) though.


  • 0
    J

    awesome solution. this is more like a math problem, actually


  • 0
    O

    Same idea as you. Below I share a shorter 8-lines implementation:

    public class Solution {
        public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
            double piv = -b / 2.0 / a;
            int n = nums.length;
            boolean direction = a < 0 || (a == 0 && b > 0);
            int[] ans = new int[n];
            for (int k = 0, i = 0, j = n - 1; k < n; k++)
                ans[direction ? k : n - k - 1] = cal(nums[(Math.abs(nums[j] - piv) > Math.abs(nums[i] - piv) ? j-- : i++)], a, b, c);
            return ans;
        }
        
        private int cal(int x, int a, int b, int c) {
            return a * x * x + b * x + c;
        }
    }
    

  • 0
    C

    Great solution! I can't believe I wrote complicated codes to find the middle point using binarySearch.

    In your codes, I think pre-compute axx+b*x+c into another array can eliminate duplicate computations.


  • 0
    I

    @codingcoconut

    Let's take a>0 as an example, it is an open-upward parabola, which means the bigger number candidates are from beginning and end. So it sets index of new array to the end, and compare two ends , then move the bigger one's pointer. It does not mean the center of original array exactly less than the beginning or the end. The reason we do this is it is easy to set two pointers at two ends then move forward to the center.


  • 0
    L

    I was wondering for the loop(a>=0) from the code,
    if write "if(a>=0)", then the whole answer would be correct.
    if write "if(a>0)" then it shows me ArrayIndexOutOfBounds.
    If anyone could tell me the reasons. From my standing, I thought a=0 doesn't matters, so the case could belong to a>0 or a<0. So I am confused.
    Appreciate!


  • 0
    L

    Brilliant, it took me a while to understand this


  • 0

    @xuyirui said in Java O(n) incredibly short yet easy to understand AC solution:

    private int quad(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
    

    Question about this -
    Why does int work here?
    a * x * x can easily get overflowed ( the final result might be still an int)


  • 0
    C

    Thumbs up!!!


  • 0
    N

    0_1486080308683_Capture.JPG
    This graph helps me understand.


  • 2

    alt text
    Always start handling from the two ends of the parabola. The difference is when a > 0, they are larger at two ends, when a < 0, they are smaller at two ends. So when a > 0, we just start to fill out the result array from end to beginning, in other case, we start filling out it from start to the end of result array.

        public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
          int n = nums.length, start = 0, end = n - 1; 
          int[] res = new int[n];
          if(a > 0){
            for(int i = n - 1; i >= 0; i--){
              int x = func(nums[start], a, b, c);    
              int y = func(nums[end], a, b, c); 
              if(x > y){
                res[i] = x;
                start++;
              } else {
                res[i] = y;
                end--;
              }
            }  
          } else {
            for(int i = 0; i < n; i++){
              int x = func(nums[start], a, b, c);    
              int y = func(nums[end], a, b, c); 
              if(x < y){
                res[i] = x;
                start++;
              } else {
                res[i] = y;
                end--;
              }
            }            
          }
          
          return res;
        }
        
        int func(int x, int a, int b, int c){
          return a * x * x + b * x + c;    
        }

Log in to reply
 

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