The real no join solution that beats 99.71% submissions


  • 2
    E

    To speed up, no join is allowed. The "no join" posts actually use self join by doing select ... from point p1, point p2.

    The trick is the follow-up: when the points are sorted, the min distance must come from adjacent points. Since the distance of adjacent points is equivalent to the difference between two rows, we can use user-defined variable to keep the value from the previous row to do the calculation.

    The code below runs in O(3n), comparing to the O(n^2) join methods (if merge join is used).

    # Initialize the prev variable to a big negative number so that the first value of difference will never get selected
    set @prev := -100000000; 
    select min(diff) as shortest
    from (select (x - @prev) as diff, @prev := x 
          from (select * from point order by x) t
         ) tt
    ;
    

  • 0
    N

    Is it possible for x to be a very small negative number like -100000001 in the point table? I am new, please help resolve my confusion.


  • 0
    E

    @newbee菜鸟 Well this would be a good point to raise at interview. Here the solution is just a demo on a possible approach.


Log in to reply
 

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