Self Crossing
Three geometric cases — the path crosses iff one of "4th edge crosses 1st", "5th meets 1st", or "6th crosses 1st" holds.
3 min read
geometry math
Problem#
A path moves north, west, south, east repeatedly with distances distance[i]. Return true iff the path self-crosses.
Examples#
[2,1,1,2]→true.[1,2,3,4]→false.
Constraints#
1 <= distance.length <= 10^5.
Approach#
It can be proved that any crossing falls into exactly one of three local cases:
- Edge i crosses edge i-3 (the spiral closes inward).
- Edge i meets edge i-4 head-on.
- Edge i crosses edge i-5 (the spiral widens then narrows).
Each case is a small inequality on three to four consecutive distances.
Solution#
class Solution {public: bool isSelfCrossing(vector<int>& d) { int n = d.size(); for (int i = 3; i < n; ++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; }};func isSelfCrossing(d []int) bool { n := len(d) for i := 3; i < n; 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}from typing import List
class Solution: def isSelfCrossing(self, d: List[int]) -> bool: 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 Falsefunction isSelfCrossing(d) { const n = d.length; for (let i = 3; i < n; 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) { int n = d.length; for (int i = 3; i < n; 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; }}function isSelfCrossing(d: number[]): boolean { const n = d.length; for (let i = 3; i < n; 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;}Editorial#
The hardest part is the proof that only these three local cases can produce a crossing — beyond i-5, the path is too far away. Once accepted, each case is a constant-time inequality, giving an O(n) walk.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#