Domain 1EasyCORE

Path Crossing

The problem asks us to determine if a path on a 2D plane crosses itself given a string of directions ('N', 'S', 'E', 'W'). We start at the origin (0, 0) and move according to the instructions in the string. The goal is to return `True` if we visit any point more than once during our traversal; otherwise, return `False`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1496. Path Crossing

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 55.3%


Problem Breakdown

The problem asks us to determine if a path on a 2D plane crosses itself given a string of directions (‘N’, ‘S’, ‘E’, ‘W’). We start at the origin (0, 0) and move according to the instructions in the string. The goal is to return True if we visit any point more than once during our traversal; otherwise, return False.

Inputs:

  • A string path consisting of characters ‘N’, ‘S’, ‘E’, ‘W’.

Outputs:

  • A boolean value indicating whether the path crosses itself.

Implicit Constraints/Edge Cases:

  • The path length is between 1 and 10,000.
  • The path will only contain valid direction characters (‘N’, ‘S’, ‘E’, ‘W’).
  • An empty string would not be a valid input based on constraints.

Intuition

A brute-force approach might involve simulating the movement and checking for revisited points after each move. However, this could lead to high time complexity as we’d need to keep track of all visited points and check against them with each new position.

The key insight is to use a set to store visited positions efficiently. By updating our current position based on the direction and adding it to the set, we can quickly determine if we’ve been there before without needing to traverse through all previous positions again.

Approach

  1. Initialize a set to keep track of visited positions.
  2. Start at the origin (0, 0) and add this position to the set.
  3. Iterate through each character in the path string:
    • Update the current position based on the direction (‘N’, ‘S’, ‘E’, ‘W’).
    • Check if the new position is already in the set of visited positions.
      • If it is, return True as we’ve crossed our path.
      • Otherwise, add the new position to the set.
  4. If the loop completes without finding a revisited position, return False.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the path string. We iterate through each character in the string once.
  • Space Complexity: O(n) in the worst case, where all positions visited are unique and stored in the set.

Solution

def isPathCrossing(path: str) -> bool:
    # Directions mapping
    directions = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
    
    # Starting position
    x, y = 0, 0
    
    # Set to track visited positions
    visited = set()
    visited.add((x, y))
    
    # Traverse the path
    for move in path:
        dx, dy = directions[move]
        x += dx
        y += dy
        
        if (x, y) in visited:
            return True
        visited.add((x, y))
    
    return False

Edge Cases Handled

  • Single Move: If the path is a single move (‘N’, ‘S’, ‘E’, or ‘W’), the function will correctly identify that it does not cross itself.
  • No Movement: If the path is empty (though invalid per constraints), the function would return False as there are no moves to make.
  • Long Path: With a path length of up to 10,000, the solution efficiently handles the maximum possible input size within acceptable time and space limits.