We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Path Crossing

Number: 1619

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given a string path consisting of the characters 'N', 'S', 'E', and 'W', each representing a move in a 2D plane (North, South, East, or West respectively), determine if the path crosses itself. That is, check whether any point on the path is visited more than once starting from the origin (0, 0).

Key Insights

  • Use a hash set to store visited coordinates.
  • Iteratively update the current position based on the move direction.
  • Check after each move if the new position has already been visited.
  • If a revisit is detected, return true immediately.
  • If the path is finished without any duplicates, return false.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the path string. Space Complexity: O(n), in the worst case we store all unique positions visited.

Solution

We simulate walking along the path starting from the origin (0, 0) and update our position according to each direction ('N', 'S', 'E', 'W'). A hash set (or equivalent data structure) is used to record every coordinate we visit. After each move, we check if the coordinate is already in the set. If it is, we return true indicating the path crosses itself. Otherwise, if we complete the path without revisiting any coordinate, we return false.

Code Solutions

# Python solution for Path Crossing
def isPathCrossing(path: str) -> bool:
    # Initialize starting position at the origin (0, 0)
    x, y = 0, 0
    # Create a set to store visited coordinates, starting with the origin
    visited = {(x, y)}
    
    # Iterate over each move in the path
    for move in path:
        # Update coordinates based on the move direction
        if move == 'N':
            y += 1
        elif move == 'S':
            y -= 1
        elif move == 'E':
            x += 1
        elif move == 'W':
            x -= 1
        
        # Check if the current coordinate has already been visited
        if (x, y) in visited:
            return True   # Path crosses itself
        # Add the new position to visited set
        visited.add((x, y))
    
    # No crossing found
    return False

# Example usage:
print(isPathCrossing("NES"))   # Expected output: False
print(isPathCrossing("NESWW")) # Expected output: True
← Back to All Questions