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 counterclockwise direction of i is greater than or equal to opposite direction of the immediate counterclockwise 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;
}
}
Concise, Readable Java Code with Comments: 0ms, O(n) Runtime with O(1) Extra Space


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

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[i2] and x[i1]<=x[i3]: return True if i>4 and x[i4]<=x[i2]<=x[i]+x[i4] and x[i1]<=x[i3]<=x[i5]+x[i1]: return True return False