My simple O(n) java solution


  • 0
    G

    public class Solution {

    // Only when we have x[i] <= x[i-2], we need to consider whether there is a cross.

    // flag indicates whether in previous step, x[i] > x[i-2]. If the flag is false, it is same as we start a new draw.

    public boolean isSelfCrossing(int[] x) {
        if(x == null || x.length < 4){return false;}
        boolean flag = true;
        for(int i = 2; i < x.length - 1; i++){
            if(x[i] == x[i-2]){
                if(x[i+1] >= x[i-1]){
                    return true;
                }
                else if(flag && i > 2 && x[i+1] + x[i-3] >= x[i-1]){
                    return true;
                }
                flag = false;
            }
            else if(x[i] < x[i-2]){
                if(x[i+1] >= x[i-1]){return true;}
                else if(flag && i > 3 && x[i] + x[i-4] >= x[i-2]){
                    if(x[i+1] + x[i-3] >= x[i-1]){
                        return true;
                    }
                }
                flag = false;
            }
            else{
                flag = true;
            }
        }
        return false;
        
    }
    

    }


Log in to reply
 

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