# Java O(n) logical solution

• ``````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;
}
}``````

• 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
___               ___
|   |             |   |
|          ==>    | ______
|______|          |_______|

*/
``````

}

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