#335

Hard

LeetCode Problem Workspace

Self Crossing

Determine if a path defined by sequential distances on a 2D plane crosses itself using array and math reasoning.

Problem Statement

You are given an integer array distance representing consecutive steps on a 2D plane. Starting at the origin (0, 0), move distance[0] meters north, then distance[1] meters west, distance[2] meters south, distance[3] meters east, and continue changing direction counter-clockwise after each step.

Return true if the path crosses itself at any point, meaning a move overlaps a previous segment. Otherwise, return false. Analyze the pattern of distances to detect intersections efficiently without full coordinate tracking.

Examples

Example 1

Input: distance = [2,1,1,2]

Output: true

The path crosses itself at the point (0, 1).

Example 2

Input: distance = [1,2,3,4]

Output: false

The path does not cross itself at any point.

Example 3

Input: distance = [1,1,1,2,1]

Output: true

The path crosses itself at the point (0, 0).

Constraints

1 <= distance.length <= 105
1 <= distance[i] <= 105

Solution Approach

Iterative Distance Comparison

Check each step against up to three previous steps to detect a crossing. Compare current distance with distances three or four steps back to identify overlap patterns that cause self-crossing.

Pattern-Based Detection

Use the array plus math pattern to classify potential crossing scenarios into three cases: simple loop, tight overlap, and extended overlap. Apply conditional checks directly on distance values without extra memory.

Constant Space Implementation

Optimize the solution to O(1) space by only tracking the last six distances. Update variables as you iterate through the array and evaluate crossing conditions in real-time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each distance is evaluated once against a constant number of prior distances. Space complexity is O(1) using fixed variables to track previous steps instead of simulating coordinates.

What Interviewers Usually Probe

Are you considering edge cases where the path touches but does not cross previous segments?
Notice if your solution handles sequences that expand then contract, creating potential intersections.
Can you simplify checks by using only the last few distances instead of full coordinate storage?

Common Pitfalls or Variants

Common pitfalls

Simulating full coordinates unnecessarily increases space usage and complexity.
Failing to check the fourth or fifth previous distance can miss overlapping loops.
Incorrectly assuming only consecutive steps can cause crossing ignores geometric patterns.

Follow-up variants

Detect self-crossing in a 3D path with directional changes in three axes.
Find the first step where the path crosses itself and return its index.
Determine if a path is self-avoiding given a repeated move sequence of arbitrary length.

FAQ

What does 'Self Crossing' mean in this problem?

It means the path on the 2D plane intersects a segment previously traversed, detected using distance comparisons in array order.

Can I use extra memory to store coordinates?

While possible, the optimal approach tracks only the last six distances, achieving O(1) space without full coordinate storage.

Why do we check distances up to three or four steps back?

Crossings can occur from loops formed by the current step overlapping segments three or four moves prior, so those comparisons catch all patterns.

Does the solution work for large arrays up to 10^5 elements?

Yes, the O(n) time and O(1) space approach scales efficiently, evaluating each step once with constant comparisons.

Is this a typical array plus math pattern problem?

Yes, it requires combining sequential array analysis with geometric reasoning to detect intersections without simulating every point.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        d = distance
        for i in range(3, len(d)):
            if d[i] >= d[i - 2] and d[i - 1] <= d[i - 3]:
                return True
            if i >= 4 and d[i - 1] == d[i - 3] and d[i] + d[i - 4] >= d[i - 2]:
                return True
            if (
                i >= 5
                and d[i - 2] >= d[i - 4]
                and d[i - 1] <= d[i - 3]
                and d[i] >= d[i - 2] - d[i - 4]
                and d[i - 1] + d[i - 5] >= d[i - 3]
            ):
                return True
        return False

Continue Practicing

#391 perfect rectangle #149 max points on a line #587 erect the fence