335. Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
?????
?   ?
???????>
    ?

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
????????
?      ?
?
?
?????????????>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
?????
?   ?
?????>

Return true (self crossing)

Solution:

Obviously, if the array length is smaller than 4, it never cross it self.

Line 3 can only cross line 0 when line 2 is <= line 0 && line 3 >=line 1

Line 4 can cross line 1 and also cross line 0, 

    a. For crossing line 1, it is the same situation with line 3 crossing line 0: x[i-1]<=x[i-3] && x[i]>=x[i-2]

   b. For crossing line 0, line3== line 1 and line 4 >= line2-line0 =>x[i-1]==x[i-3] && x[i]>=x[i-2]-x[i-4]. 

Line 5 can cross line 2 and line 0

   a. For crossing line 2, it is the same: x[i-1]<=x[i-3] && x[i]>=x[i-2]

   b. For crossing line 0,  Line 2 > line 0, && line 3 must > line 1, line 4 must between lin2-line 0 and line 2, then line 5 must > line 3-line 1 => x[i-2]>x[i-4] && x[i-1]>=x[i-3]-x[i-5] && x[i-1]<=x[i-3] && x[i]>=x[i-2]-x[i-4].

 You will get a more clear picture if you draw it on a paper. 

For any line > 5, basically it is the same with line 5, you can rotate your drawing and you will understand why it is the same. 

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