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:
- The current line segment Xi can only intersect (or touch) with line segments numbered Xi-3 , Xi-4 , Xi-5 ,... and so on.
- 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
- 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.
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.
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.
Categories: PROBLEM SOLVING