Path Crossing

Difficulty: Easy | Acceptance: 62.60% | Paid: No Topics: Hash Table, String

Given a string path, where path[i] = ‘N’, ‘S’, ‘E’ or ‘W’, each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.

• Examples
• Constraints
• Approach 1: Simulation with Hash Set
• Approach 2: Brute Force Simulation

Examples

Example 1:

Input: path = "NES"
Output: false
Explanation: Notice that the path doesn't cross any point more than once.

Example 2:

Input: path = "NESWW"
Output: true
Explanation: The path starts at (0,0), goes to (0,1), (1,1), (1,0), and then back to (0,0). The point (0,0) is visited twice, so the path crosses itself.

Constraints

1 <= path.length <= 10⁴
path[i] is either 'N', 'S', 'E', or 'W'.

Simulation with Hash Set

Intuition We can simulate the walk step-by-step, keeping track of every coordinate we visit. If we ever arrive at a coordinate that is already in our set of visited locations, we know the path has crossed itself.

Steps

• Initialize a set data structure to store visited coordinates. Add the starting point (0, 0).
• Initialize variables x and y to 0 representing the current position.
• Iterate through each character in the path string:
  • Update x or y based on the direction (N, S, E, W).
  • Check if the new coordinate (x, y) exists in the set.
  • If it exists, return true immediately.
  • Otherwise, add the new coordinate to the set.
• If the loop finishes without finding a duplicate, return false.

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        visited = set()
        visited.add((0, 0))
        x, y = 0, 0
        
        for direction in path:
            if direction == 'N':
                y += 1
            elif direction == 'S':
                y -= 1
            elif direction == 'E':
                x += 1
            elif direction == 'W':
                x -= 1
            
            if (x, y) in visited:
                return True
            
            visited.add((x, y))
        
        return False

Complexity

• Time: O(n), where n is the length of the path. We iterate through the path once, and set operations are O(1) on average.
• Space: O(n), to store the visited coordinates in the worst case where no crossing occurs.
• Notes: This is the most efficient approach for this problem.

Brute Force Simulation

Intuition We simulate the walk and store every visited coordinate in a list. For every new step, we scan through the entire list of previously visited coordinates to check for a collision.

Steps

• Initialize a list to store visited coordinates. Add the starting point (0, 0).
• Initialize variables x and y to 0.
• Iterate through the path:
  • Update x and y based on the direction.
  • Iterate through the list of visited coordinates.
  • If the current (x, y) matches any coordinate in the list, return true.
  • Add the current (x, y) to the list.
• If the loop finishes, return false.

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        visited = [(0, 0)]
        x, y = 0, 0
        
        for direction in path:
            if direction == 'N':
                y += 1
            elif direction == 'S':
                y -= 1
            elif direction == 'E':
                x += 1
            elif direction == 'W':
                x -= 1
            
            if (x, y) in visited:
                return True
            
            visited.append((x, y))
        
        return False

Complexity

• Time: O(n²), where n is the length of the path. For each of the n steps, we scan the list of visited coordinates, which grows up to size n.
• Space: O(n), to store the visited coordinates.
• Notes: This approach is conceptually simple but inefficient for large inputs compared to the Hash Set approach.