A plain solution with O(n) time and O(1) space


  • 0
    E

    I use xline to denote the maximum horizontal line and yline to denote the maximum vertical line.

    for each x[i]:
    i%2 === 0 means vertical line
    i%2 === 1 means horizontal line

    There are only two cases where the result does NOT cross: spin from outside to inside or spin from inside to outside. From inside to outside means line becomes larger and larger. [1, 2, 3, 4] falls into this category. From outside to inside means the opposite. For example, [4, 3, 2, 1] falls into this category. These two cases can be combined. If combined, only first spin from inside to outside and then from outside to inside.

    As long as it spins out, everything works fine. If we hit the end of the array, we are good to return false. Once we have shorter line, we need to consider "spin in" case.

    Add preyline and prexline to denote the constraint for "spin in" case when we have "spin out" first.

    var isSelfCrossing = function(x) {
        var len = x.length;
        if(len < 4){
            return false;
        }
        var yline = x[0];
        var xline = x[1];
        var preyline = 0;
        var prexline = 0;
        var i = 2;
        var j;
        while(i < len){
            if((i%2 === 0 && x[i] <= yline) || (i%2 === 1 && x[i] <= xline)){
                i++;
                break;
            }
            else{
                if(i %2 === 0){
                    preyline = yline;
                    yline = x[i];
                }
                else{
                    prexline = xline;
                    xline = x[i];
                }
                i++;
            }
        }
        if(i === len){
            return false;
        }
        i--;
        /* consider spin in case */
        if(i%2 === 0){
            if(x[i] < (yline-preyline)){
                yline = x[i];
            }
            else{
                xline = xline - prexline;
            }
        }
        else{
            if(x[i] < xline - prexline){
                xline = x[i];
            }
            else{
                yline = yline - preyline;
            }
        }
       for(j = i+1; j < len; j++){
           if(j%2 === 0){
               if(x[j] >= yline){
                   return true;
               }
               else{
                   yline = x[j];
               }
           }
           else{
               if(x[j] >= xline){
                   return true;
               }
               else{
                   xline = x[j];
               }
           }
       }
       return false;
    };

Log in to reply
 

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