Self Crossing - Leetcode Solution

The Self Crossing problem on LeetCode is a problem that requires you to determine whether a given set of points, representing the coordinates of a person's movement, intersects with any of their previous trajectories. The problem statement can be found here: https://leetcode.com/problems/self-crossing/

To solve this problem, we will first need to understand the different types of self-intersections that can occur:

• Case 1: The line segment of the current point crosses the line segment of the 3rd previous point, forming a loop or a "C" shape.
• Case 2: The line segment of the current point overlaps with the line segment of the 4th previous point, forming an "X" shape.
• Case 3: The line segment of the current point crosses the line segment of the 5th previous point or beyond, forming a more complex figure.

With these cases in mind, we can start by iterating through the array of points, starting at the 5th index, keeping track of the previous 5 points that we have passed. For each point, we check for the different cases of self-intersection.

To check for Case 1, we calculate the cross product of the vector between the current point and the 3rd previous point, and the vector between the 5th previous point and the 4th previous point. If the cross product is positive, it means that the two vectors are turning in opposite directions and thus forms a loop or a "C" shape.

To check for Case 2, we compare the current point with the 4th previous point to see if there is any overlap, which can occur if the current point is within the range of the 4th previous point's x or y coordinates.

To check for Case 3, we calculate the cross product of the vector between the current point and the 4th previous point, and the vector between the previous point and the point before that. If the cross product is positive, it means that the two vectors are turning in opposite directions and thus forms a more complex figure.

If any of the cases are detected, we return true, meaning that there is a self-intersection. Otherwise, we continue iterating through the point array. If we reach the end of the array without any self-intersections, we return false.

Here is the Python code for the solution:

class Solution:
    def isSelfCrossing(self, x: List[int]) -> bool:
        for i in range(5, len(x)):
            if x[i] >= x[i-2] and x[i-1] <= x[i-3]: # Case 1
                return True
            elif i >= 6 and x[i-2] >= x[i-4] and x[i-3] == x[i-1] and x[i] + x[i-4] >= x[i-2]: # Case 2
                return True
            elif i >= 7 and x[i-3] > x[i-5] and x[i-1] > x[i-3] and x[i-2] > x[i-4] and x[i] >= x[i-2]-x[i-4] and x[i-1] <= x[i-3]+x[i-5] and x[i-1]+x[i-5] >= x[i-3]: # Case 3
                return True
        return False

Note that this solution has a time complexity of O(n) and a space complexity of O(1), where n is the length of the point array.

1