A simple python solution with explanation


  • 4
    H

    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
    

Log in to reply
 

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