You are given an array of integers distance.
You start at the point (0, 0) on an X-Y plane, and you move distance[0] meters to the north, then distance[1] meters to the west, distance[2] meters to the south, distance[3] meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.
Return true if your path crosses itself or false if it does not.
Example 1:
Input: distance = [2,1,1,2] Output: true Explanation: The path crosses itself at the point (0, 1).
Example 2:
Input: distance = [1,2,3,4] Output: false Explanation: The path does not cross itself at any point.
Example 3:
Input: distance = [1,1,1,2,1] Output: true Explanation: The path crosses itself at the point (0, 0).
Constraints:
1 <= distance.length <= 1051 <= distance[i] <= 105The Self Crossing problem asks whether a path defined by sequential movement distances crosses itself. The movement typically follows a repeating direction pattern (north, west, south, east), which means the path gradually forms expanding or contracting loops. A brute-force geometric check comparing every segment with previous ones would be inefficient.
The key insight is that only a few recent segments can create a crossing due to the fixed turning pattern. By analyzing geometric relationships between the current segment and several previous segments, we can detect specific crossing configurations such as a segment intersecting the one three steps earlier or overlapping with earlier boundaries.
An optimal approach scans the array once while checking a small set of geometric conditions between nearby segments. This leads to a highly efficient solution with linear time complexity and constant extra space, making it suitable for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single-pass geometric pattern detection | O(n) | O(1) |
NeetCodeIO
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Self Crossing is considered a challenging geometry and array problem and has appeared in advanced coding interviews. Companies may use it to evaluate a candidate’s ability to recognize patterns, optimize beyond brute force, and reason about geometric constraints.
The optimal approach scans the distance array once and checks geometric relationships between the current segment and a few previous segments. Because the path turns in a fixed pattern, only nearby segments can intersect. This allows the problem to be solved in O(n) time with constant extra space.
No complex data structure is required for the optimal solution. The algorithm relies on comparing values in the input array and analyzing geometric relationships between recent path segments. This keeps the space complexity at O(1).
A brute-force method would compare each new segment with many previous segments, leading to O(n^2) complexity. This becomes inefficient for large inputs. The optimized approach works because the movement pattern limits possible intersections to only a few recent segments.