Java O(n) logical solution


  • 0
    K
    public class Solution {
        public boolean isSelfCrossing(int[] x) {
            /* Base case */
            if (x.length < 4) return false;
            /* Regular case */
            int trend = 2; // trend=2: pending
            int[] path = new int[5];
            /* Handle first 4 edge */
            if (x[2] <= x[0] && x[3] >= x[1]) 
                return true; 
            else if (x[2] > x[0] && x[3] > x[1]) 
                trend = 0; // trend=0: up, the loop keep going outward
            else if (x[2] <= x[0]) 
                trend = 1; // trend=1: down, the loop keep shrinking
            
            /* Save first 4 path :) */
            path[1] = x[0]; path[2] = x[1]; path[3]= x[2]; path[4] = x[3];
            
            for (int i = 4; i < x.length; i++) {
                moveForward(x[i], path); // Push current edge to path[4]
                if (trend == 1) { // DOWN
                    if (path[4] >= path[2]) return true; // If not shrinking, will go self-cross
                }
                else if (trend == 0) { // UP
                    if (path[4] <= path[2]) { //if current edge shorter than opposite edge, trend will go DOWN or PENDING
                        if (path[4] + path[0] < path[2])  // Check if overlap with the parallel edge.
                            trend = 1; // OK, change trend to down
                        else 
                            trend = 2; // Special condition, change status to pending.
                    }
                }
                else if (trend == 2) { // PENDING
                    if (path[4] + path[0] < path[2])
                        trend = 1; // OK, change status to down
                    else 
                        return true;
                }
            }
            return false;
        }
        
        /* :) not beautiful */
        public void moveForward(int newEdge, int[] path) {
            path[0] = path[1]; path[1] = path[2]; path[2] = path[3]; path[3] = path[4];
            path[4] = newEdge;
        }
    }

  • 2
    C

    public class SelfCrossing {

    enum State{ TRAN,DIV,CON }
    
    public boolean isSelfCrossing(int[] x) {
    
        Function<Integer,Integer> X = i -> i < 0 ? 0 : x[i];
    
        State state = State.DIV;
    
        for( int i = 2; i < x.length; ++i )
            switch (state){
                case DIV:
                    if( X.apply(i) > X.apply(i-2) )
                        state = State.DIV;
                    else if( X.apply(i) >= X.apply(i-2) - X.apply(i-4) )
                        state = State.TRAN;
                    else
                        state = State.CON;
                    break;
                case CON:
                    if( X.apply(i) >= X.apply(i-2) )
                        return true;
                    state = State.CON;
                    break;
                case TRAN:
                    if( X.apply(i) >= X.apply(i-2) - X.apply(i-4) )
                        return true;
                    state = State.CON;
                    break;
            }
    
        return false;
    }
    
         /*DIV
             ___   |
            |   |  |
            |   |  |
            |______|
        */
    
        /*TRAN
                 ___              ___
                |   |            |   | _
                |   |  |   ==>   |   |  |
                |______|         |______|
    
    
         */
    
        /* CON
                 ___               ___
                |   |             |   |
                |          ==>    | ______
                |______|          |_______|
    
         */
    

    }


Log in to reply
 

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