BiruLyu
8/17/2017 - 2:19 PM

## 335. Self Crossing(#1).java

``````class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
for(int i=3, l=x.size(); i<l; i++) {
// Case 1: current line crosses the line 3 steps ahead of it
if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true;
// Case 2: current line crosses the line 4 steps ahead of it
else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true;
// Case 3: current line crosses the line 6 steps ahead of it
else if(i>=5 && x[i-2]>=x[i-4] && x[i]+x[i-4]>=x[i-2] && x[i-1]<=x[i-3] && x[i-1]+x[i-5]>=x[i-3]) return true;
}
return false;
}

/*               i-2
case 1 : i-1┌─┐
└─┼─>i
i-3

i-2
case 2 : i-1 ┌────┐
└─══>┘i-3
i  i-4      (i overlapped i-4)

case 3 :    i-4
┌──┐
│i<┼─┐
i-3│ i-5│i-1
└────┘
i-2

*/
``````
``````/*
There are only 3 scenarios where it won’t cross itself.
The distances of the moves parallel to each other keeps going up (growing spiral).
The distances of the moves parallel to each other keeps going down (shrinking spiral).
The distances of the moves parallel to each other first keeps going up, then keeps going down (shrinking spiral inside of the growing spiral), and never goes up.
from  https://leetcode.com/discuss/88038/java-o-n-o-1-0ms-solution-with-explanation

*/

public class Solution {
public boolean isSelfCrossing(int[] x) {
int n = x.length;
if (n < 4) return false;
int t1 = 0, t2 = x[0], t3 = x[1], t4 = x[2], t5;
boolean increase = t4 > t2 ? true : false;
for (int i = 3; i < n; i++) {
t5 = x[i];
if (increase && t3 >= t5) {
if (t5 + t1 < t3 || i + 1 < n && x[i + 1] + t2 < t4)
increase = false;
else if (i + 1 < n)
return true;
}
else if (!increase && t3 <= t5)
return true;
t1 = t2;
t2 = t3;
t3 = t4;
t4 = t5;
}
return false;
}
}``````