Java Solution based on spiral direction status


  • 11
    J

    I solved this problem based on spiral direction status. Here is the accepted code:

    public static boolean isSelfCrossing(int[] x) {
    	if (x.length < 4)
    		return false;
    	
    	boolean inside = false;
    	for (int i = 3; i < x.length; i++) {
    		if(inside) {
    			if (x[i] >= x[i - 2])
    				return true;
    			continue;
    		}
    				
    		if(x[i-1] > x[i-3])
    			continue;
    
    		int x5 = i>=5 ? x[i-5] : 0;
    		int x4 = i>=4 ? x[i-4] : 0;
    		if(x[i-1] >= x[i-3] - x5) {
    			if(x[i] >= x[i-2] - x4)
    				return true;
    		}else {
    			if(x[i] >= x[i-2])
    				return true;
    		}
    		inside=true;
    	}
    	return false;
    }
    

    For this question, to keep the line not crossed, it can be in following conditions:

    1. Keep spiraling outside.
    2. Keep spiraling inside.
    3. Not crossing during transition from outside spiral into inside spiral.

    And one observation is once it starts to spiral inside, it will never spiral outside.

    Based on this observation, we keep one flag: inside which is initialized to false,

    During spiraling outside, and inside, the check is very simple: just check x[i] < x[i-2] for inside spiral. In outside spiral phase, as long as x[i-1] > x[i-3], it's not possible to cross in this step.

    Once x[i-1] > x[i-3] condition is broken, we will trigger the transition period: In this period, it has two conditions,

    1. If this turn back line is towards line x[i-5] (possible cross x[i-5])
    2. If this turn back line is not towards line x[i-5]. in that case, it will go towards x[i-3] instead.

    We need to calculate the max line for x[i] for the two cases.

    When i<4 and i<5 corner case, to avoid many if/else we just prepend two additional steps as if they are moving 0 length. So assign x4 and x5 to 0 respectively.

    This solution compare to other solution based on 3 different crossing condition, it's slight better as it will only look back x[i-4] and x[i-4] during transition period (once only). In other two phases, it will only compare two edges.


  • 0
    V

    based on your idea, I simplify the code to below:

        public boolean isSelfCrossing(int[] x) {
            if(x == null || x.length <= 3) return false;
            return !isSpinIn(x, 0, x.length - 1) && !isSpinOut(x, 0, x.length - 1);
        }
        // spin-in, if cross, return false.
        private boolean isSpinIn(int[] x, int from, int end) {
            for(int i = from, j = from + 2; j <= end; i++, j++)
                if(i != from && x[i] <= x[j]) 
                    return false;
            return true;
        }
        // spin-out / spin-out transit to spin in.
        private boolean isSpinOut(int[] x, int from, int end) {
            for(int i = from, j = from + 2; j < end; i++, j++)
                if(x[i] >= x[j]) 
                    // Not crossing during transition from outside spiral into inside spiral and the violated part is a valid spin-in
                    return (i - 2 >= 0 && x[j] < (x[i] - x[i-2]) || i - 1 >= 0 && x[j+1] < (x[i + 1] - x[i-1])) && isSpinIn(x, i, end);
            return true;
        }
    

Log in to reply
 

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