Solution: Self Crossing
Explore how to determine if a path on an X-Y plane crosses itself by analyzing movement distances in a structured counterclockwise pattern. Learn to apply mathematical comparisons instead of tracking coordinates, identifying specific crossing scenarios. This lesson enables you to detect self-crossings efficiently with O(n) time and O(1) space complexity, enhancing your problem-solving in math and geometry coding challenges.
We'll cover the following...
Statement
You are given an array of integers, distance, where each element represents the length of a move you will make on an X-Y plane. You start at the origin, which is point distance[0] meters north, distance[1] meters west, distance[2] meters south, distance[3] meters east, and continue this pattern in a counterclockwise direction. Each step follows the sequence—north, west, south, east—repeating as long as there are remaining distances in the array.
Your task is to determine whether this path crosses itself at any point. This means checking whether you revisit any previously visited position (including the origin or any other point) at any step. Return TRUE if the path intersects itself, and FALSE otherwise.
Constraints: ...