Self Crossing solution and explanation
8 more videos on this problem
LeetCode 335. Self CrossingHappy Coding · 19:34 · 1K views
Leetcode [335] Self CrossingSDE Skills · 27:43 · 796 views
Leetcode--335 self crossing (math)You Wu · 14:35 · 747 views
【每日一题】335. Self Crossing, 12/11/2019Huifeng Guan · 37:19 · 438 views
335. Self Crossing (Leetcode Hard)Programming Live with Larry · 1:15:11 · 420 views
Leetcode Question 335 "Self Crossing" in JavaGhumman Tech · 11:31 · 331 views
335. Self Crossing | Leetcode Unlocked - PythonLeetcode Unlocked · 6:45 · 31 views
No Sound Leetcode 335: Self CrossingExtremeProgrammer · 2:59 · 30 views
LeetCode 335: Self CrossingAlitaCode · 29:09 · 19 views
The problem
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] <= 105
Approach overview
Problem 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 1: Geometric Analysis of Path Crossing
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.
def isSelfCrossing(distance):
n = len(distance)
if n < 4:
return False
for i in range(3, n):
if distance[i] >= distance[i-2] and distance[i-1] <= distance[i-3]:
return True
if i >= 4 and distance[i-1] == distance[i-3] and distance[i] + distance[i-4] >= distance[i-2]:
return True
if i >= 5 and distance[i-2] >= distance[i-4] and distance[i] + distance[i-4] >= distance[i-2] and distance[i-1] <= distance[i-3] and distance[i-1] + distance[i-5] >= distance[i-3]:
return True
return Falsepublic boolean isSelfCrossing(int[] distance) {
int n = distance.length;
if (n < 4) return false;
for (int i = 3; i < n; i++) {
if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3])
return true;
if (i >= 4 && distance[i - 1] == distance[i - 3] && distance[i] + distance[i - 4] >= distance[i - 2])
return true;
if (i >= 5 && distance[i - 2] >= distance[i - 4] && distance[i] + distance[i - 4] >= distance[i - 2] &&
distance[i - 1] <= distance[i - 3] && distance[i - 1] + distance[i - 5] >= distance[i - 3])
return true;
}
return false;
}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 current line crosses the line 3 steps before.
- It touches the line 4 steps before, forming a square.
- The current line crosses the line 5 steps before.
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.
Approach 2: Using Coordinate Tracking
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.
function isSelfCrossing(distance) {
const s = new Set(["0,0"]);
let x = 0, y = 0, i = 0;
const directions = [[0, 1], [-1, 0], [0, -1], [1, 0]];
for (const d of distance) {
let [dx, dy] = directions[i];
for (let j = 0; j < d; j++) {
x += dx;
y += dy;
let key = `${x},${y}`;
if (s.has(key)) return true;
s.add(key);
}
i = (i + 1) % 4;
}
return false;
}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.
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 3: Default Approach
class Solution {
public:
bool isSelfCrossing(vector<int>& distance) {
vector<int> d = distance;
for (int i = 3; i < d.size(); ++i) {
if (d[i] >= d[i - 2] && d[i - 1] <= d[i - 3]) return true;
if (i >= 4 && d[i - 1] == d[i - 3] && d[i] + d[i - 4] >= d[i - 2]) return true;
if (i >= 5 && d[i - 2] >= d[i - 4] && d[i - 1] <= d[i - 3] && d[i] >= d[i - 2] - d[i - 4] && d[i - 1] + d[i - 5] >= d[i - 3]) return true;
}
return false;
}
};public class Solution {
public bool IsSelfCrossing(int[] x) {
for (var i = 3; i < x.Length; ++i)
{
if (x[i] >= x[i - 2] && x[i - 1] <= x[i - 3]) return true;
if (i > 3 && x[i] + x[i - 4] >= x[i - 2])
{
if (x[i - 1] == x[i - 3]) return true;
if (i > 4 && x[i - 2] >= x[i - 4] && x[i - 1] <= x[i - 3] && x[i - 1] + x[i - 5] >= x[i - 3]) return true;
}
}
return false;
}
}func isSelfCrossing(distance []int) bool {
d := distance
for i := 3; i < len(d); i++ {
if d[i] >= d[i-2] && d[i-1] <= d[i-3] {
return true
}
if i >= 4 && d[i-1] == d[i-3] && d[i]+d[i-4] >= d[i-2] {
return true
}
if i >= 5 && d[i-2] >= d[i-4] && d[i-1] <= d[i-3] && d[i] >= d[i-2]-d[i-4] && d[i-1]+d[i-5] >= d[i-3] {
return true
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Geometric Analysis of Path Crossing | The time complexity is |
| Using Coordinate Tracking | The time complexity of this solution is |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Self Crossing easy or hard?
Self Crossing is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the limited geometric crossing patterns and translating them into precise distance comparisons rather than simulating the entire path.
How to solve Self Crossing in O(n)?
Iterate through the distance array starting from index 3 and check three crossing cases involving the last 3–5 segments. Conditions compare values such as x[i] >= x[i-2] and x[i-1] <= x[i-3] to detect intersections. Each step performs constant-time comparisons, giving an overall O(n) scan with O(1) memory.
What is the best approach for Self Crossing?
The best approach is geometric pattern analysis with O(n) time and O(1) space. Instead of storing coordinates, the algorithm checks distance relationships between the last few moves. These comparisons detect three possible crossing configurations that occur due to the repeating north‑west‑south‑east movement pattern.
Is Self Crossing asked at Google/Amazon/Meta?
Self Crossing has appeared in interviews at major tech companies including Google and Amazon because it tests geometric reasoning and pattern recognition rather than standard data structures. Candidates must identify path intersection cases without building the full coordinate grid.
What data structure is used in Self Crossing?
The optimal solution mainly relies on the input array and mathematical comparisons between recent elements. A simulation-based approach may additionally use coordinate pairs or line segments to track the path, but the most efficient method requires no extra data structures.
What is the time complexity of Self Crossing?
The optimal solution runs in O(n) time because it scans the distance array once while checking a constant number of geometric conditions at each step. Space complexity is O(1) since only a few previous distances are needed for the comparisons.
Self Crossing Python or Java solution approach?
Python and Java implementations typically follow the geometric analysis method. The code iterates through the distance array and evaluates the three crossing cases using simple conditional checks. Both languages achieve O(n) time and O(1) space with only a few integer comparisons.