Problem statement

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

Solution

If we do not have intersections, our data will look in general like two spirals, first: increasing one, and then decreasing. Increasing means a[i] > a[i-2], decreasing means a[i] < a[i+2]. There are some special cases we need to process, about 15 lines of code.

There is another smart idea: in fact if we have segment number i, it can be intersected only with segments with numbers i+3, i+4 and i+5. So we can iterate over segments and check conditions for intersection. Let a, b, c, d, e, f be lengths of 6 adjacent segments. Then we have:

  1. 0 < c <= a and d >= b > 0 means that we have intersection of i and i+3.
  2. b == d != 0 and 0 < c <= a + e means that we have intersection of i and i+4.
  3. a + e >= c > 0 and b + f >= d > 0 and b < d and e < c means that we have intersection of i and i+5.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def isSelfCrossing(self, x):
        n = len(x)
        x += [0]*6
        for i in range(n):
            a, b, c, d, e, f = x[i:i+6]
            if 0 < c <= a and d >= b > 0: return True
            if b == d != 0 and 0 < c <= a + e: return True
            if a + e >= c > 0 and b + f >= d > 0 and b < d and e < c: return True
        
        return False