# 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:

```text
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

| Item | Meaning |
|---|---|
| Input | `distance`, a list of positive integers |
| Output | `true` if the path crosses itself |
| Direction order | North, west, south, east, then repeat |
| Required time | `O(n)` |
| Required extra space | `O(1)` |

Function shape:

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

## Examples

Example 1:

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

Movement:

```text
2 north
1 west
1 south
2 east
```

The fourth segment crosses the first segment.

Example 2:

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

The path keeps expanding outward and does not cross.

Example 3:

```text
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:

```text
O(n)
```

space to store segments, and:

```text
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:

| Segment | Reason |
|---|---|
| `i - 1` | Adjacent segment, shares an endpoint |
| `i - 2` | Parallel direction |
| Very old segments before `i - 5` | The spiral shape makes the crossing already detectable earlier |

So we only need to check three crossing patterns.

Let:

```text
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:

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

Example:

```text
[2, 1, 1, 2]
```

At `i = 3`:

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

Check:

```text
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:

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

Example:

```text
[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:

```python
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:

```text
[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:

| Case | Meaning |
|---|---|
| Case 1 | Current segment crosses segment three moves earlier |
| Case 2 | Current segment touches or overlaps segment four moves earlier |
| Case 3 | Current segment crosses segment five moves earlier during inward spiral |

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We only inspect recent distances |

## Implementation

```python
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:

```python
x = distance
```

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

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

The first condition checks crossing with segment `i - 3`:

```python
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`:

```python
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`:

```python
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:

```python
return False
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[2,1,1,2]` | Standard crossing |
| `[1,2,3,4]` | Expanding path |
| `[1,1,1,1]` | Boundary crossing |
| Length less than 4 | Cannot self-cross |
| `[1,1,2,1,1]` | Inward crossing |
| Long outward path | No crossing |
| `[2,2,3,3,2,2]` | Inward spiral crossing |