# Re-post: 2 O(N) C++ 0ms solutions

• The first solution is well described in KuangYuan's post and the idea is to enumerate all the self-crossing cases. Basically, there are three cases
Case1: self-crossing is formed by the last 4 lines (like a closed rectangle)
Case 2: self-crossing is formed by the last 5 lines (still like a closed rectangle with one edge having two moves)
Case 3: self-crossing is formed by the last 6 lines (like two overlapped rectangles)

``````class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
int len = x.size(),i;
for(i=3; i<len;++i)
{
if(x[i]>=x[i-2] && x[i-1] <= x[i-3]) return true; // case 1, the consecutive four lines form a cross
if(i>3 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true; // case 2, the consecutive five lines form a cross
if(i>4 && x[i-2]>=x[i-4] && x[i-4]+x[i]>=x[i-2] && x[i-1]<=x[i-3] && x[i-5] + x[i-1]>=x[i-3]) return true;// case 3, the consecutive six lines form a cross
}
return false;
}
};
``````

The second solution is to categorize all the non-self-crossing cases: basically we can only have two valid cases: one is "grow spiral" (which means the curve expands like spiral and there is no boundaries in x and y axis) and the other is "shrink spiral" (which means the spiral curve becomes smaller and smaller and the boundaries in x and y axis are the last move in that direction). The self-crossing cases can only happen in the "shrink" case and it happens only when x[i]>=x[i-2]. The "grow" case can become a "shrink" case and that only happens when x[i]<=x[i-2]. The "shrink" case can not change to a "grow" case.
In the solution, we use a bool grow_spiral to indicate whether the current one is a "grow spiral". if before x[i], it is a "shrink spiral", we only need to check if a self-crossing happen (i.e. x[i]>=x[i-2]); if it is a "grow spiral", we check if x[i] changes from "grow" to "shrink" (i.e. x[i]<=x[i-2]), we need to update the boundary x[i-1] (in some cases, it can be x[i-1]-x[i-3]).

``````class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
int len = x.size(), i;
if(len<=3) return false;
bool grow_spiral;

for(i=3, grow_spiral = x[2]>x[0]; i<len;++i)
{
if(!grow_spiral && x[i]>=x[i-2]) return true;//if it is a "shrink" case before x[i] and cross happens
if(grow_spiral && x[i]<=x[i-2])
{ // if it is a grow case, and x[i] changes it to shrink
grow_spiral = false;
x[i-1] = x[i] + (i>=4?x[i-4]:0)<x[i-2]? x[i-1]:x[i-1]-x[i-3];// update boundary
}
}
return false;
}
};
``````

My special thank goes to hohomi for pointing out one bug in Solution 2 and I believe I fixed it.

• What a great idea the solution 2. Can you please explain in detail the "update boundary" step. I am having a hard time understanding that.

• The valid case you summarize is not enought, it can also be grow first and shrink secondly.

• Suppose if(grow_spiral && x[i]<=x[i-2]) will detect the grow->shrink case you mentioned, Thanks,

• Your idea is brilliant! I changed the boundary update condition, for those who also has difficulty in understanding yours.

``````class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
bool grow=x.size()>2?x[2]>x[0]:true;
for(int i=3;i<x.size();++i){
if(!grow&&x[i]>=x[i-2]) return true;
if(grow&&x[i]<=x[i-2]){
grow=false;
if(x[i]==x[i-2]||(i>3&&(x[i]>=x[i-2]-x[i-4])))
x[i-1]-=x[i-3];
}
}
return false;
}
};
``````

• brilliant!!!

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