💬 Discord
Sign In
NeetCode #76LC-1496EasyArrays & Hashing
← Back to All Problems

#76 · #1496 · Path Crossing(判断路径是否相交)

📌 Problem Statement & Constraints

Given a string path where each segment is 'N', 'S', 'E' or 'W', starting at the origin, determine whether the path crosses itself at any point. Constraints: 1 <= path.length <= 10^4.

💡 Core Algorithmic Approaches

  1. Simulate the walk, recording every visited coordinate in a hash set.
  2. Before moving to a new coordinate, check whether it is already in the set. If so, the path crosses itself.
  3. The set must include the starting point (0, 0) so that returning to the origin is detected as a crossing.
  4. Each step is O(1), so the whole simulation is linear.

💻 Benchmark Python3 Implementation

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        x = y = 0
        seen = {(0, 0)}                    # the start counts as visited
        move = {"N": (0, 1), "S": (0, -1), "E": (1, 0), "W": (-1, 0)}
        for ch in path:
            dx, dy = move[ch]
            x += dx
            y += dy
            if (x, y) in seen:
                return True                # revisited -> crossing
            seen.add((x, y))
        return False

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one step per character with O(1) hash operations.
💾 Space Complexity
O(n) for the visited set.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to seed the set with (0, 0): a path returning to the origin would not be flagged, e.g. "NESW".
  • Using a list of visited points: membership becomes O(n), giving O(n^2) overall.
  • Checking before moving instead of after: the crossing is detected at the destination cell, so the test must happen after the update.
  • Storing only one coordinate: both x and y are needed to identify a cell.