335. Self Crossing

  • 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
2
3
4
5
6
7
8
9
10
Example 1:
Given x =
[2, 1, 1, 2]
,
┌───┐
│ │
└───┼──>


Return true (self crossing)
1
2
3
4
5
6
7
8
9
10
11
Example 2:
Given x =
[1, 2, 3, 4]
,
┌──────┐
│ │


└────────────>

Return false (not self crossing)
1
2
3
4
5
6
7
8
9
Example 3:
Given x =
[1, 1, 1, 1]
,
┌───┐
│ │
└───┼>

Return true (self crossing)

https://discuss.leetcode.com/topic/38635/the-best-submission-in-c-searching-for-the-crossing-patterns-is-the-key

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
2
3
4
5
6
7
8
9
10
bool isSelfCrossing(int* x, int size)
{
for(int i = 3; i < size; i++)
{
if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true;
if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true;
if(i>=5 && x[i-2]-x[i-4]>=0 && x[i]>=x[i-2]-x[i-4] && x[i-1]>=x[i-3]-x[i-5] && x[i-1]<=x[i-3]) return true;
}
return false;
}

In C++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
for(int i = 3; i < x.size(); i++) {
if(x[i-1]<=x[i-3] && x[i]>=x[i-2]) return true;
if(i>3 && x[i]+x[i-4]>=x[i-2] && x[i-1]==x[i-3]) return true;
if(i>4 && x[i-1]+x[i-5]>=x[i-3] && x[i-1]<=x[i-3] && x[i]+x[i-4]>=x[i-2] && x[i-4]<=x[i-2]) return true;
}
return false;
}
};

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

C++ simple solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution
{
public:
bool isSelfCrossing(vector<int>& x)
{
x.insert(x.begin(), 4, 0);

int len = x.size();
int i = 4;

// outer spiral
for (; i < len && x[i] > x[i - 2]; i++);

if (i == len) return false;

// check border
if (x[i] >= x[i - 2] - x[i - 4])
{
x[i - 1] -= x[i - 3];
}

// inner spiral
for (i++; i < len && x[i] < x[i - 2]; i++);

return i != len;
}
};

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

image

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

1
2
3
4
if (x[i] >= x[i - 2] - x[i - 4])
{
x[i - 1] -= x[i - 3];
}

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
2
3
4
5
6
7
8
9
10
11
12
13
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]).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.


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

Another python…

Checking out every six pack.

Solution 1

1
2
3
4
def isSelfCrossing(self, x):
return any(d >= b > 0 and (a >= c or a >= c-e >= 0 and f >= d-b)
for a, b, c, d, e, f in ((x[i:i+6] + [0] * 6)[:6]
for i in xrange(len(x))))

Solution 2

1
2
3
4
5
6
7
def isSelfCrossing(self, x):
b = c = d = e = 0
for a in x:
if d >= b > 0 and (a >= c or a >= c-e >= 0 and f >= d-b):
return True
b, c, d, e, f = a, b, c, d, e
return False
1
2
3
4
5
6
7
8
9
10
11
12
13
Explanation

b b
+----------------+ +----------------+
| | | |
| | | | a
c | | c | |
| | a | | f
+-----------> | | | <----+
d | | | | e
| | |
+-----------------------+
d

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
2
3
4
5
6
7
8
9
class Solution(object):
def isSelfCrossing(self, x):
"""
:type x: List[int]
:rtype: bool
"""
return any(d >= b > 0 and (a >= c or a >= c - e >= 0 and f >= d - b) \
for a, b, c, d, e, f in ((x[i:i+6] + [0] *6)[:6] \
for i in xrange(len(x))))
谢谢你,可爱的朋友。