Self Crossing

Self Crossing looks like a geometry nightmare — a line spiraling around a plane — but the trick is to refuse to draw it. The whole problem collapses into comparing each move against a few of its recent neighbours.

The slow way first

The literal approach: simulate the walk, build the list of line segments, and test every new segment against every old one for intersection. That is O(n²) segment-pair tests, plus fiddly floating-point-free geometry to get the intersection math right. It works, but it is a lot of error-prone code for what turns out to be a tiny pattern.

The question to ask: when a left-turning spiral crosses itself, what does that look like locally? It turns out there are only three shapes a fresh segment can make as it bumps into an earlier one — and each is a simple comparison of distances.

The idea: three cases on the distance array

Forget coordinates. Keep only the distances x. At move i, compare x[i] to the 3rd, 4th, and 5th previous distances. Those neighbours capture the only three ways the spiral can touch its own tail:

• Case 1 — the new line crosses the one three steps back (the spiral is shrinking).
• Case 2 — the new line exactly meets a parallel earlier line, then a fifth line closes the gap.
• Case 3 — the spiral grows again and the sixth line crosses back across the first.

Because each case only looks back a fixed number of distances, the whole scan is O(n) with no geometry at all.

Walk through it

Step through the animation with x = [1, 1, 2, 2, 1, 1]. The pointer i advances along the distance array, and at each stop we run the cases in order until one fires:

• i = 3 — Case 1 checks x[3]=2 >= x[1]=1 (yes) and x[2]=2 <= x[0]=1 (no). The shrink condition fails, so Case 1 misses and we advance.
• i = 4 — Now i >= 4, so Case 2 switches on. Case 1 fails immediately (x[4]=1 >= x[2]=2 is false), and Case 2 fails because x[3]=2 == x[1]=1 is false. Advance again.
• i = 5 — Now i >= 5, so Case 3 switches on. Cases 1 and 2 both miss, but Case 3 chains four comparisons — x[3]=2 >= x[1]=1, x[5]+x[1]=2 >= x[3]=2, x[4]=1 <= x[2]=2, x[4]+x[0]=2 >= x[2]=2 — and all four hold, so the re-grown sixth segment crosses the first and we return True.

Notice how the guards matter: Case 2 only became checkable at i = 4 and Case 3 at i = 5. Earlier moves simply did not have enough history to form those shapes.

Pseudocode

for i from 3 to n-1:
    # Case 1: current line crosses the line 3 steps back
    if x[i] >= x[i-2] and x[i-1] <= x[i-3]:
        return True
    # Case 2: current line lands exactly on a parallel earlier line
    if i >= 4 and x[i-1] == x[i-3] and x[i] + x[i-4] >= x[i-2]:
        return True
    # Case 3: a re-growing spiral crosses the first line again
    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

The Python solution

def is_self_crossing(x):
    n = len(x)
    for i in range(3, n):
        # Case 1: 4th line crosses the 1st
        if (x[i] >= x[i - 2] and
                x[i - 1] <= x[i - 3]):
            return True
        # Case 2: 5th line meets the 1st
        if (i >= 4 and x[i - 1] == x[i - 3] and
                x[i] + x[i - 4] >= x[i - 2]):
            return True
        # Case 3: 6th line crosses the 1st
        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

• The loop starts at i = 3 because you need at least four moves before a crossing is possible.
• Case 1 fires when the spiral shrinks: the new line reaches back far enough (x[i] >= x[i-2]) while the previous line had already closed in (x[i-1] <= x[i-3]).
• Case 2 needs i >= 4. It handles the exact-touch shape where x[i-1] == x[i-3] and the new line plus the line four back spans the gap.
• Case 3 needs i >= 5. It is the re-growing spiral: each of the five comparisons confirms the sixth line swings back across the first.
• If no case ever fires, the path never crosses, so we return False.

Complexity

We use no extra space — the answer is a constant-window comparison over the input array, so it is O(1) beyond the input itself.

When this pattern shows up

Practice