Machine Learning, AI and Programming

Leetcode : Self Crossing

Problem Statement


The brute force approach would be to store the starting and the ending co-ordinates for each line segment in an array A and then for the current segment, check if it intersects or "touches" any one of the previous line segments present in the array A. The run-time and space complexity of this approach is O(N2) where N is the number of line segments. Can we do this in a run-time complexity of O(N) and space complexity of O(N) with O(1) extra space ?

BTW since we are only provided with the lengths of line segments, we can easily convert these lengths into (X, Y) co-ordinates.

The important observations we make here are:

  1. The current line segment Xi can only intersect (or touch) with line segments numbered Xi-3 , Xi-4 , Xi-5 ,... and so on.
  2. Due to the cyclic property of the line segments, if the line segment Xi intersects another line segment Xj where j < i-5, then Xi also intersects the line segments Xi-5
  3. The last property ensures that we need to scan for possible intersections only for Xi-3 , Xi-4 and Xi-5

The second property can be proved by observing that Xi and Xi-6 are along the same axis but move towards opposite direction, thus Xi can only touch the near end of Xi-6. But the near end of Xi-6 also touches Xi-5, thus Xi also touches Xi-5.

X7 touches X1

Xi and Xi-7 are along orthogonal axis, thus Xi can either intersect Xi-7 or can touch one of its end. But Xi-7 and Xi-5 are both along the same axis and also Xi-5 lies in between Xi and Xi-7, thus Xi cannot intersect Xi-7 without intersecting Xi-5 first.

X7 intersects X0

By induction we can prove that if Xi intersects or touches any Xi-k for k < 7, then it also intersects or touches Xi-5. For e.g. if k is even then it touches Xi-k+1 and if k is odd it intersects Xi-k+2. Now apply induction on Xi-k+1 and Xi-k+2.

Interestingly we can determine whether any path crosses or not without converting the line segments to co-ordinates as used in the following very short Python code:

class Solution(object):
    def isSelfCrossing(self, x):
        if len(x) < 4:
            return False
        for i in range(3, len(x)):
            a = x[i] >= x[i-2] and x[i-1] <= x[i-3]
            b = i >= 4 and x[i] + x[i-4] >= x[i-2] and x[i-2] > x[i-4] and x[i-1] == x[i-3]
            c = i >= 5 and x[i] + x[i-4] >= x[i-2] and x[i-2] > x[i-4] and x[i-1] + x[i-5] >= x[i-3] and x[i-3] > x[i-5] and x[i-1] <= x[i-3]
            if a or b or c:
                return True
        return False

The boolean variables 'a', 'b' and 'c' track whether Xi crosses Xi-3, Xi-4 and Xi-5 respectively.


Tags: , , , ,

Leave a Reply