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] <= 105Problem Overview: You receive an array x where each value represents the distance moved in a counter‑clockwise direction sequence: north, west, south, east, repeating. Starting at the origin, determine whether the path ever crosses itself. The challenge is detecting intersections while walking the path without explicitly building a full geometric grid.
Approach 1: Using Coordinate Tracking (Segment Intersection) (Time: O(n), Space: O(n))
This method simulates the walk and stores the coordinates of each visited segment. Every step produces a vertical or horizontal line segment because movement always alternates directions. After computing the new endpoint, check whether the current segment intersects any earlier segment that is not directly adjacent. Intersection checks compare ranges of x and y coordinates between perpendicular segments. This approach is straightforward because it mirrors the actual path geometry, but it stores all coordinates and performs repeated intersection checks, which increases constant factors even though the theoretical complexity is linear.
Approach 2: Geometric Analysis of Path Crossing (Time: O(n), Space: O(1))
The optimal approach avoids storing coordinates and instead analyzes distance patterns. Since movement cycles through four directions, a crossing can only happen in specific geometric configurations involving the last 3–5 moves. While iterating the array, compare the current distance with previous distances to detect three common crossing patterns: the current line crossing the line three steps earlier, the current line overlapping the line four steps earlier, and the complex spiral case where it crosses the line five steps earlier. Each condition can be checked using simple comparisons like x[i] >= x[i-2] and x[i-1] <= x[i-3]. Because only a few previous values are needed, the algorithm runs in constant space while scanning the array once.
This pattern‑based reasoning relies heavily on properties of axis‑aligned movement and repeating direction cycles. The logic is rooted in geometry and coordinate relationships but implemented efficiently using simple comparisons on an array. Understanding why the crossings occur requires visualizing how the path gradually spirals inward or outward.
Recommended for interviews: Interviewers expect the geometric analysis solution. The coordinate‑tracking simulation shows you understand the path and intersection detection, but the O(1) space pattern analysis demonstrates stronger algorithmic insight. It uses observations from mathematical constraints of the movement sequence and reduces the problem to constant‑time comparisons per step.
This approach relates to understanding how the current path intersects any of the previous paths. It uses a combination of geometric constraints to check whether the path crosses itself within a certain number of steps. The solution involves verifying conditions when the line segments created by the sequence of movements intersect.
This Python function iterates through the distance list starting from the fourth distance. It checks three specific situations where a path can cross itself:
The time complexity is O(n), where n is the length of the distance array, as we have to go through each element. The space complexity is O(1) since no additional data structures requiring space proportional to input size are used.
Another approach is to simulate every movement and track the current position on the Cartesian plane while storing all the previous positions in a set to check for crossings using the coordinates directly. This method manually maintains a set of segments on the path that can identify crossings.
This JavaScript function maintains the current position and records every unique position on the plane into a set. If an incoming position already exists in the set, a path crossing is detected.
JavaScript
The time complexity of this solution is O(n * d), where d is the average or maximum distance traveled in a single move and n is the length of the distance array. The space complexity is O(n * d) considering the worst case where all unique positions need to be stored.
| Approach | Complexity |
|---|---|
| Geometric Analysis of Path Crossing | The time complexity is |
| Using Coordinate Tracking | The time complexity of this solution is |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Coordinate Tracking with Segment Intersection | O(n) | O(n) | When implementing a straightforward geometric simulation or when debugging path behavior visually |
| Geometric Pattern Analysis | O(n) | O(1) | Best choice for interviews and production due to constant space and direct pattern checks |
LeetCode 335. Self Crossing • Happy Coding • 1,871 views views
Watch 9 more video solutions →Practice Self Crossing with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor