Readable and Simple Solution in Java 1ms


  • 0
    H

    Hello guys,

    The essential idea is to find the distance to the N-2 segment and to the N-4 segment and then compare the distances to length of the current segment.

    At the beginning, I got messed up with the handling of directions. Then I realized, there has nothing to do with direction ! Rotating the graph, you will have the same configuration.

    One special case to take care is the one when you reach the 5th segment where you can close the rectangle with the starting one.

    There you go,

    public class Solution {
        public boolean isSelfCrossing(int[] x) {
            if(x.length < 4) return false;
            for(int i = 3; i < x.length; i++) {
                int increase = x[i];
    
                if(cross(increase, distanceToN_2(x, i))) {
                    return true;
                } 
                
                if(i==4 && x[i-1] == x[i-3] && increase >= x[i-4]) {
                    return true;
                }
    
                if(i > 4 && cross(increase, distanceToN_4(x, i))) {
                    return true;
                }
            }
            return false;
        }
        
        private boolean cross(int increase, int distance) {
            return distance > 0 && increase >= distance;
        }
        
        //return -1 if impossible to cross
        private int distanceToN_2(int[] x, int i) {
            int distance = x[i - 2];
            if(x[i-1] > x[i-3]) {
                return -1;
            } else {
                return distance;
            }
        }
        
        //return -1 if impossible to cross
        private int distanceToN_4(int[] x, int i) {
            int distance = x[i-2] - x[i-4];
            if(x[i-1] > x[i-3]) {
                return -1;
            } else if(x[i-5] + x[i-1] < x[i-3]) {
                return -1;
            } else {
                return distance;
            }
        }
    }

Log in to reply
 

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