# A simple python solution with explanation

• This is based on dong.wang.1694's second solution with a little modification.

The basic idea is like this:

1. When expanding, we never collide.

2. When shrinking, we collide when we go back too far. For example, if two steps ago, we went upward for 8, this time we can't go down for more than 7 or it is a collision.

3. The tricky part is when transitioning from expanding to shrinking, we may get an early collision!!

``````class Solution(object):
def isSelfCrossing(self, x):

n = len(x)
x.append(0.5)        # let x[-1] = 0.5
if n < 4: return False
grow = x[2] > x[0]

for i in range(3,n):
if not grow and x[i] >= x[i-2]: return True
if grow and x[i] <= x[i-2]:
grow = False
if x[i] + x[i-4] >= x[i-2]:
x[i-1] -= x[i-3]
return False
``````

Graph

``````                                          +------------+
+---------+                           |            |
|         |                           |            |
|         |                           |            |
|         |                           |            |
|       i-4  <----+                   |            |
i-2 |         |       |                   |            +
|         |       |                   |
|                 |i                  |
|                 |                   |         <---------------+
|                 |                   |                         |
+---------+-------+                   |                         |
^                           |                         |
|                           +-------------------------+
|

x[i] + x[i-4] >= x[i-2]                  x[i] + x[i-4] < x[i-2]
Then, possible early collision,          nothing has to be changed
pretend we have started from
the plus sign point
``````

when x[3] == x[1], we have to deal with a very special case. So we pretend we have started from a point 0.5 to the left of the origin making this case identical to what we have discussed above.

``````        1
+------------+
|            |
|            |
|            |0
|            |
|            |
2 |            |
|            +
|
|
|            ^
|            |
|            |
+------------+
3
``````

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