Path Crossing: Hash Set Coordinate Tracking

Given a string path where path[i] is one of 'N', 'S', 'E', or 'W', representing moves on a 2D grid starting from the origin (0, 0), return true if the path crosses itself at any point. In other words, return true if at any time you revisit a coordinate you have already been to.

This is LeetCode 1496: Path Crossing, and it is a clean introduction to using hash sets for coordinate tracking. The pattern it teaches applies to any problem where you need to detect revisited states in a sequence of moves.

Why this problem matters

At its core, this problem is about state tracking. You have a moving point on an infinite grid, and you need to know if it ever returns to somewhere it has been. This same idea shows up in cycle detection, simulation problems, and robotics path planning. The tool you reach for is a hash set, and Path Crossing gives you a minimal, distraction-free setting to practice that tool.

Once you internalize this pattern, you will recognize it in problems like "Happy Number" (detecting cycles in sequences), "Contains Duplicate" (detecting repeated elements), and "Robot Return to Origin" (a simpler variant that only checks if you return to the start).

The key insight

You do not need to store the entire grid or build any complex data structure. You only need to remember which coordinates you have visited. A set gives you O(1) lookup for "have I been here before?" At each step, compute your new position, check the set, and either return true (crossing detected) or add the position and continue.

The coordinate can be stored as a tuple (x, y) in Python or as a string "x,y" in languages without hashable tuples. The choice of representation does not matter as long as equality checks work correctly.

The solution

def is_path_crossing(path: str) -> bool:
    x, y = 0, 0
    visited = {(0, 0)}

    for direction in path:
        if direction == 'N':
            y += 1
        elif direction == 'S':
            y -= 1
        elif direction == 'E':
            x += 1
        else:
            x -= 1

        if (x, y) in visited:
            return True
        visited.add((x, y))

    return False

The function starts at the origin and adds it to the visited set. Then for each character in the path string, it updates the coordinates based on the direction. After moving, it checks whether the new position already exists in the set. If so, the path has crossed itself and we return True immediately. Otherwise, we add the new position to the set and keep going. If we exhaust all moves without finding a repeated coordinate, the path never crosses, and we return False.

Visual walkthrough

Let's trace through the path "NESW" step by step. Watch how the visited set grows with each move, and how we detect the crossing the moment we try to revisit a coordinate.

The key moment is move 4. When we move West from (1,0), we land back at (0,0). The set lookup tells us instantly that this coordinate has been visited before. We do not need to scan through a list or compare against every previous position. The hash set gives us that answer in O(1) time.

Complexity analysis

Time is O(n) where n is the length of the path string. We process each character exactly once, and each set lookup and insertion is O(1) on average. In the worst case (no crossing), we iterate through all n characters.

Space is O(n) because the visited set can hold up to n + 1 coordinates (the starting position plus one for each move). If the path never crosses, every position is unique, and the set grows to size n + 1.

The building blocks

1. Direction-to-coordinate mapping

moves = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
x, y = 0, 0
for d in path:
    dx, dy = moves[d]
    x, y = x + dx, y + dy

This is the fundamental pattern for converting a sequence of directional moves into coordinates. You maintain a running (x, y) position and apply deltas based on the direction. You will reuse this in "Robot Return to Origin," "Walking Robot Simulation," and any grid simulation problem.

2. Hash set membership checking

visited = {(0, 0)}
if (x, y) in visited:
    return True
visited.add((x, y))

This is the "have I seen this before?" pattern. You maintain a set of all states encountered so far, and you check membership before adding new states. The same pattern applies to cycle detection in linked lists (with node references instead of coordinates), detecting duplicate values in arrays, and checking for repeated states in game simulations.

Edge cases

• Single character path: A path like "N" can never cross because you only visit two points: the origin and (0,1).
• Path that returns to origin: "NESW" or "NS" followed by "NS". The moment you step onto any previously visited coordinate, not just the origin, you return true.
• Long path with no crossing: A path like "NNNN..." that moves in one direction indefinitely never crosses. The set grows linearly but no lookup ever hits.
• Immediate crossing: "NES" does not cross, but "NSN" crosses at (0,0) on the third move because after N and S you are back at origin, then N revisits (0,1).
• Empty path: An empty string means you never move. No crossing is possible, return false.

From understanding to recall

The logic here is simple: track positions, check for repeats. But under interview pressure, people fumble the details. Do you initialize the set with the origin or not? Do you check before or after updating coordinates? Do you use (x, y) or f"{x},{y}" in your language? These small decisions need to be automatic.

Spaced repetition locks them in. You write the coordinate tracking loop from memory, verify it against the correct solution, and repeat at increasing intervals. After a few rounds, the pattern is second nature. You see "detect if a path revisits a point" in a problem description, and the hash set solution flows out without hesitation.

Related posts

• Contains Duplicate - Same hash set membership pattern applied to array elements instead of coordinates
• Happy Number - Cycle detection using a hash set to track previously seen states in a sequence
• Linked List Cycle - Detecting revisited nodes in a linked list, another "have I been here before?" problem

CodeBricks breaks Path Crossing into its coordinate tracking and hash set membership building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a state-tracking problem shows up in your interview, you do not think about it. You just write it.