Path Crossing (LeetCode 1496): Detecting a Revisit With a Set of Points

by linkjobai

HTML

<h1>Path Crossing (LeetCode 1496): Detecting a Revisit With a Set of Points</h1>
<p>Starting at the origin, follow a string of moves N, S, E, W one unit at a time. Return true if the path ever visits the same point twice. It is a simulation problem about representing state cleanly.</p>
<h2>Approach</h2>
<p>Keep the current (x, y) and a set of visited points, starting with (0, 0). After each move, if the new point is already in the set, return true; otherwise add it.</p>
<pre><code class="language-python">def is_path_crossing(path):
    step = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
    x = y = 0
    seen = {(0, 0)}
    for c in path:
        dx, dy = step[c]
        x, y = x + dx, y + dy
        if (x, y) in seen:
            return True
        seen.add((x, y))
    return False
</code></pre>
<h2>Complexity</h2>
<p>O(n) time and O(n) space.</p>
<h2>Interview pitfalls</h2>
<p>Remember to add the origin before the first move, or a path like NS will be missed. Use tuples, not lists, as set keys.</p>
<h2>Practicing out loud</h2>
<p>The hard part of easy problems is explaining them crisply under time pressure. Practice narrating the approach, the complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see <a href="https://www.linkjob.ai/">Linkjob.ai</a>.</p>

CSS

body{max-width:760px;margin:2em auto;font-family:system-ui;line-height:1.6;padding:0 1em}
pre{background:#f4f4f4;padding:1em;overflow:auto}