- 24.4%

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

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.

1 | Example 1: |

1 | Example 2: |

1 | Example 3: |

The best submission in C searching for the crossing patterns is the key

After drawing a few crossing cases ourselves, we can simply find out there are two basic patterns:

- x[i-1]<=x[i-3] && x[i]>=x[i-2] the ending circle line cross the beginning circle line in one circle;
- i>=5 && x[i-1]<=x[i-3] && x[i]>=x[i-2]-x[i-4] the second line of the next circle cross the the beginning of the previous circle between two adjacent circles;

But still that is not over yet, how about some special cases? How about the first line of the next circle and the previous circle? Yeah, the beginning line of the next circle can overlap the the first line of the previous circle - another two adjacent circles case:

1 | i>=4 && x[i-1]==x[i-3] && x[i]>=x[i-2]-x[i-4] |

Quite straightforward. Then we can test our patterns now, however soon we will find out that the second cases is not strong enough to cover all possible situations - the second line of the next circle crossing the previous circle at the its first line

[3,3,3,2,1,1] is an example here, so x[i-2]>=x[i-4] then must be added to our conditions;

[3,3,4,4,10,4,4,,3,3] is another typical example for x[i-3]<=x[i-1]+x[i-5] condition, which also should be added to make the constrained conditions stronger;

At last, we make it! Bang! End of story with a very terse, clean and efficient code as follows.

Updated: 2016-09-12 For better and easier reasoning, here is the thinking thread.

Suppose i is the current line, then:

- i and i-3 can cross
- i and i-4 can cross
- i and i-5 can cross

no more or no less just exactly the right combination.

Now it’s time for us to restrict the conditions to make them just happen.

i and i-3

1 | i>=i-2 && i-1<=i-3 |

i and i-4

1 | i+i-4>=i-2 && i-1==i-3 |

i and i-5

1 | i+i-4>=i-2 && i-2>=i-4 && i-1+i-5>=i-3 && i-1<=i-3 |

In C

1 | bool isSelfCrossing(int* x, int size) |

In C++

1 | class Solution { |

https://discuss.leetcode.com/topic/43622/c-simple-solution

C++ simple solution

1 | class Solution |

https://discuss.leetcode.com/topic/43622/c-simple-solution/2

This is why we need to “check border” and ajust the x[i-1]

1 | if (x[i] >= x[i - 2] - x[i - 4]) |

Hope that helps~

https://discuss.leetcode.com/topic/38084/re-post-2-o-n-c-0ms-solutions

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

0ms, 11.44%, 29/29, April.26th, 2016

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)

1 | class Solution { |

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]).

1 | class Solution { |

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

https://discuss.leetcode.com/topic/38068/another-python

Another python…

Checking out every six pack.

Solution 1

1 | def isSelfCrossing(self, x): |

Solution 2

1 | def isSelfCrossing(self, x): |

1 | Explanation |

Draw a line of length a. Then draw further lines of lengths b, c, etc. How does the a-line get crossed? From the left by the d-line or from the right by the f-line, see the above picture. I just encoded the criteria for actually crossing it.

Two details:

- In both cases, d needs to be at least b. In the first case to cross the a-line directly, and in the second case to get behind it so that the f-line can cross it. So I factored out d >= b.
- The “special case” of the e-line stabbing the a-line from below is covered because in that case, the f-line “crosses” it (note that even if there is no actual f-line, my code uses f = 0 and thus still finds that “crossing”).

44ms, 34.78%, 29/29, April.26th, 2016

https://leetcode.com/discuss/88153/another-python

1 | class Solution(object): |