LeetCode 335: Self Crossing

Problem Restatement

We are given an integer array distance.

We start at point (0, 0) on a 2D plane.

The movement directions repeat in this order:

north -> west -> south -> east -> north -> ...

After each move, the direction turns counter-clockwise.

Return true if the path crosses itself. Otherwise, return false.

The problem asks for a one-pass algorithm using O(1) extra space. The official statement defines this exact movement order and asks whether the path crosses itself.

Input and Output

Function shape:

def isSelfCrossing(distance: list[int]) -> bool:
    ...

Examples

Example 1:

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

Movement:

2 north
1 west
1 south
2 east

The fourth segment crosses the first segment.

Example 2:

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

The path keeps expanding outward and does not cross.

Example 3:

Input: distance = [1,1,1,1]
Output: true

The fourth segment touches or crosses the first segment, so the answer is true.

First Thought: Store All Segments

A direct method is to build every line segment.

For each new segment, compare it with all previous segments.

Since every segment is axis-aligned, checking intersection is not difficult.

But this uses:

O(n)

space to store segments, and:

O(n^2)

time in the worst case.

The problem asks for one pass and O(1) extra space, so we need to use the fixed movement pattern.

Key Insight

Because directions always rotate counter-clockwise, the current segment can only cross a small number of recent segments.

At step i, the new segment cannot cross:

So we only need to check three crossing patterns.

Let:

x = distance

At index i, check whether segment i crosses one of these older segments:

1. Segment i - 3.
2. Segment i - 4.
3. Segment i - 5.

These are the only possible crossing cases for this movement pattern.

Crossing Case 1: Current Segment Crosses Segment i - 3

This is the most common case.

Condition:

x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]

Example:

[2, 1, 1, 2]

At i = 3:

x[3] = 2
x[1] = 1
x[2] = 1
x[0] = 2

Check:

x[3] >= x[1]  -> 2 >= 1
x[2] <= x[0]  -> 1 <= 2

So the fourth segment crosses the first segment.

Crossing Case 2: Current Segment Meets Segment i - 4

This is the case where the current segment overlaps or touches the segment four moves ago.

Condition:

i >= 4 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] >= x[i - 2]

Example:

[1, 1, 1, 1]

The fourth segment reaches the first segment.

This is a boundary crossing, so it should return true.

Crossing Case 3: Current Segment Crosses Segment i - 5

This handles the inward spiral case.

Condition:

i >= 5
and x[i - 2] >= x[i - 4]
and x[i] + x[i - 4] >= x[i - 2]
and x[i - 1] <= x[i - 3]
and x[i - 1] + x[i - 5] >= x[i - 3]

This pattern appears when the path first expands, then turns inward and crosses an older side.

Example:

[1, 1, 2, 1, 1]

or longer inward-spiral variants can trigger this kind of crossing.

Algorithm

Scan distance from left to right.

For every index i >= 3, check the three crossing cases.

If any case is true, return True.

If the scan finishes, return False.

Correctness

The path consists of axis-aligned segments whose directions repeat north, west, south, east.

For a new segment at index i, adjacent segments cannot create a new self-crossing because they share endpoints by construction. The segment two steps before is parallel. Due to the fixed counter-clockwise movement, any possible first crossing must involve one of the segments i - 3, i - 4, or i - 5.

The algorithm checks all three possible crossing configurations:

If one of these conditions holds, the current segment intersects a previous segment, so the path crosses itself.

If none of these conditions ever holds, then no segment crosses any earlier segment. Since every possible first crossing must match one of the three checked patterns, the path never crosses itself.

Therefore, the algorithm returns true exactly when the path crosses itself.

Complexity

Implementation

class Solution:
    def isSelfCrossing(self, distance: list[int]) -> bool:
        x = distance

        for i in range(3, len(x)):
            if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
                return True

            if (
                i >= 4
                and x[i - 1] == x[i - 3]
                and x[i] + x[i - 4] >= x[i - 2]
            ):
                return True

            if (
                i >= 5
                and x[i - 2] >= x[i - 4]
                and x[i] + x[i - 4] >= x[i - 2]
                and x[i - 1] <= x[i - 3]
                and x[i - 1] + x[i - 5] >= x[i - 3]
            ):
                return True

        return False

Code Explanation

We use a shorter variable name:

x = distance

Then scan from index 3, because fewer than four moves cannot self-cross:

for i in range(3, len(x)):

The first condition checks crossing with segment i - 3:

if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
    return True

The second condition checks the boundary case with segment i - 4:

if (
    i >= 4
    and x[i - 1] == x[i - 3]
    and x[i] + x[i - 4] >= x[i - 2]
):
    return True

The third condition checks the inward spiral case with segment i - 5:

if (
    i >= 5
    and x[i - 2] >= x[i - 4]
    and x[i] + x[i - 4] >= x[i - 2]
    and x[i - 1] <= x[i - 3]
    and x[i - 1] + x[i - 5] >= x[i - 3]
):
    return True

If no crossing pattern appears, the path never crosses itself:

return False

Testing

def run_tests():
    s = Solution()

    assert s.isSelfCrossing([2, 1, 1, 2]) == True
    assert s.isSelfCrossing([1, 2, 3, 4]) == False
    assert s.isSelfCrossing([1, 1, 1, 1]) == True

    assert s.isSelfCrossing([1]) == False
    assert s.isSelfCrossing([1, 1]) == False
    assert s.isSelfCrossing([1, 1, 2]) == False

    assert s.isSelfCrossing([1, 1, 2, 1, 1]) == True
    assert s.isSelfCrossing([3, 3, 4, 2, 2]) == False
    assert s.isSelfCrossing([1, 2, 3, 4, 5, 6]) == False
    assert s.isSelfCrossing([2, 2, 3, 3, 2, 2]) == True

    print("all tests passed")

run_tests()

Test meaning: