Watch 10 video solutions for Self Crossing, a hard level problem involving Array, Math, Geometry. This walkthrough by NeetCodeIO has 958,987 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |