Leetcode 335: Self Crossing

https://leetcode.com/problems/self-crossing/description/

Notes:

This question is labeled as Math, so we need to find the "rules".

One solution is to find the possible patterns of crossing, and there are three possible patterns:

(1): the ith edge crosses with the (i-3)th edge;

(2): the ith edge crosses with the (i-4)th edge;

(3): the ith edge crosses with the (i-5)th edge;

The condition for

(1) x[i] >= x[i-2] && x[i-1] <= x[i-3];

(2) i>3 && x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2];

(3) i>4 && x[i-2] >= x[i-4] && x[i-1] <= x[i-3] && x[i-1] + x[i-5] >= x[i-3] && x[i] + x[i-4] >= x[i-2]

See the code below:

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int n = x.size();
     //   if(n<4) return false;
        for(int i=3; i<n; ++i) {
            if(x[i-1] <= x[i-3] && x[i] >= x[i-2]) return true;//the ith crosses with the (i-3)th;
            if(i>3 && x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2]) return true;//the ith crosses with the (i-4)th; overlap
            if(i>4 && x[i-1] <= x[i-3] && x[i-4] <= x[i-2] && x[i] + x[i-4] >= x[i-2] && x[i-1] + x[i-5] >= x[i-3])
                return true; //the ith crosses with the (i-5)th;
        }
        return false;
    }
};

Another way to solve this question is that: if there is no self-crossing, it must be one of the following three categories:

1): a growing spiral; which requires x[i] > x[i-2]

2): a shrinking spiral; which requires x[i] < x[i-2]

3): from a growing spiral to a shrinking one

See the code below:

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int n = x.size();
        if(n<4) return false;
        bool grow = x[2] > x[0];//growning spiral
        for(int i=3; i<n; ++i) {
            if(!grow && x[i] >= x[i-2]) return true;
            if(grow && x[i] <= x[i-2]) {//from growning to shrinking spiral
                grow = false;
                if(x[i] == x[i-2] || (i>3 && x[i] + x[i-4] >= x[i-2])) {
                    x[i-1] -= x[i-3];//update boundary due to switch
                } 
            }
        }
        return false;
    }
};