Self Crossing

hard math geometry

Problem

A path moves in counter-clockwise directions (N, W, S, E, N…) for d[i] units each. Return true if it crosses itself.

Inputdistance = [2,1,1,2]

Outputtrue

The 4th leg touches the 1st — crossing.

distance (comma-separated)

def is_self_crossing(d):
    n = len(d)
    for i in range(3, n):
        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-3] >= d[i-1] and            d[i-1] + d[i-5] >= d[i-3] and d[i] + d[i-4] >= d[i-2]:
            return True
    return False

function isSelfCrossing(d) {
  for (let i = 3; i < d.length; i++) {
    if (d[i] >= d[i-2] && d[i-1] <= d[i-3]) return true;
    if (i >= 4 && d[i-1] === d[i-3] && d[i] + d[i-4] >= d[i-2]) return true;
    if (i >= 5 && d[i-2] >= d[i-4] && d[i-3] >= d[i-1] &&
        d[i-1] + d[i-5] >= d[i-3] && d[i] + d[i-4] >= d[i-2]) return true;
  }
  return false;
}

class Solution {
    public boolean isSelfCrossing(int[] d) {
        for (int i = 3; i < d.length; i++) {
            if (d[i] >= d[i-2] && d[i-1] <= d[i-3]) return true;
            if (i >= 4 && d[i-1] == d[i-3] && d[i] + d[i-4] >= d[i-2]) return true;
            if (i >= 5 && d[i-2] >= d[i-4] && d[i-3] >= d[i-1] &&
                d[i-1] + d[i-5] >= d[i-3] && d[i] + d[i-4] >= d[i-2]) return true;
        }
        return false;
    }
}

bool isSelfCrossing(vector& d) {
    for (int i = 3; i < (int)d.size(); i++) {
        if (d[i] >= d[i-2] && d[i-1] <= d[i-3]) return true;
        if (i >= 4 && d[i-1] == d[i-3] && d[i] + d[i-4] >= d[i-2]) return true;
        if (i >= 5 && d[i-2] >= d[i-4] && d[i-3] >= d[i-1] &&
            d[i-1] + d[i-5] >= d[i-3] && d[i] + d[i-4] >= d[i-2]) return true;
    }
    return false;
}

Explanation

Instead of drawing the path and checking line intersections, we notice that a crossing can only happen in a few fixed shapes involving the most recent legs, so we just compare the latest distances against the ones just before them.

There are three patterns to catch. The first: the current leg d[i] reaches back far enough (d[i] >= d[i-2]) while the turn before was tight (d[i-1] <= d[i-3]) — the spiral folds in and touches an earlier edge.

The second pattern (needs i >= 4) is when the path closes exactly: d[i-1] == d[i-3] and d[i] + d[i-4] >= d[i-2]. The third (needs i >= 5) handles a wider overlap where the current leg, helped by an even earlier one, reaches past the leg four steps back.

We scan once from i = 3 onward, and the moment any pattern matches we return true. If we finish the loop with no match, the path never crosses.

Example: distance = [2, 1, 1, 2]. At i = 3, d[3]=2 >= d[1]=1 and d[2]=1 <= d[0]=2, so the first pattern fires and we return true.

Time: O(n) Space: O(1)