Skip to main content
Talentd

Self Crossing - Solution & Explanation

HardArrayMathGeometry7 min readAsked at: Bloomberg
Practice this problem

Problem Statement

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 <= 105
  • 1 <= 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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaScript

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoC#

Python

Java

C++

Go

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Geometric Analysis of Path Crossing

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.

Using Coordinate Tracking

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Coordinate Tracking with Segment IntersectionO(n)O(n)When implementing a straightforward geometric simulation or when debugging path behavior visually
Geometric Pattern AnalysisO(n)O(1)Best choice for interviews and production due to constant space and direct pattern checks

Video Solution

LeetCode 335. Self Crossing • Happy Coding • 1,970 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Self Crossing with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays