My Java solution

  • 4

    This problem reminds me of an old snake game where snake eats its own tail..

    It pretty clear that once x[i]<=x[i-2] the snake will become 'trapped' and eventually will eat itself. From there on we need to find conditions of when this happens. The easiest one is x[i]>=x[i-2]. The other 2 are a little tricker:

    First one is when snake catches it's tail at 0 degree angle. For example [1,1,2,1,1]

    Second one when it catches it's tail at 90 degree angle. For example [1,1,2,2,1,1]

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

Log in to reply

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