Concise, Readable Java Code with Comments: 0ms, O(n) Runtime with O(1) Extra Space


  • 0
    E
    public class Solution {
        public boolean isSelfCrossing(int[] x) {
            //if x has less than 4 variables, it will not cross, even if the array is [1,0,1] OJ says it is false
            if( x == null || x.length < 4 ) 
            {
                return false;
            }
            
            for( int i = 3; i < x.length; i++ )
            {
                /*normal case, if current path is greater than or equal to opposite path 
                AND if previous path is less than or equal to its opposite path,
                there is a cross ( i.e. i is going north`EAST >= WEST AND SOUTH <= NORTH )*/
                if( x[ i ] >= x[ i - 2 ] && x[ i - 1 ] <= x[ i - 3 ] )  
                {
                    return true;
                }
                
                else if( i >= 4 )   
                {
                    /*out of 5 paths, if the most recent i path and current i path added together equal the one path going in the opposite direction 
                    AND the immediate counter-clockwise direction of i is greater than or equal to opposite direction of the immediate counter-clockwise direction of i,
                     there is a cross (i.e. i is going north then ( PREV_NORTH + CURR_NORTH == SOUTH ) AND ( WEST >= EAST ) )*/
                    if( x[ i ] + x[ i - 4 ] == x[ i - 2 ] && x[ i - 3 ] >= x[ i - 1 ] ) 
                    {
                        return true;
                    }
                }
            }
            return false;
        }
    }

  • 0

    Fails for example [2,2,3,3,2,2].

    (I'll ask to get that added)

    Edit: And fails [2,2,3,1,1].


  • 0
    E

    Okay, I'll look into it. I don't think the second one [2,2,3,1,1] is a cross.


  • 0

    Not sure why you're saying that about the second one...


  • 0
    M

    Hi StefanPochmann, I am also confused why the second one is a cross, could you give a brief explanation? Maybe I misunderstood this question. Thanks.


  • 0

    @Mimimu Huh? There is no cross in that case. Which is why Entyl's solution fails, because it returns true.


  • 0
    C
    This post is deleted!

  • 0
    C

    I modified your code a bit, now this should work:

    def isSelfCrossing(self, x):
        if len(x)<4:
            return False
        if len(x) > 4 and x[3]==x[1] and x[2]<=x[4]+x[0]:
            return True
        for i in xrange(3,len(x)):
            if x[i]>=x[i-2] and x[i-1]<=x[i-3]:
                return True
            if i>4 and x[i-4]<=x[i-2]<=x[i]+x[i-4] and x[i-1]<=x[i-3]<=x[i-5]+x[i-1]:
                return True
        return False
    

  • 0

    Thanks Stefan for catching it. I have just added both of your test cases.


Log in to reply
 

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