algoadvance

You are given a string path, where path[i] is the iᵗʰ direction that you will move. The direction can be:

• ‘N’ for north,
• ‘S’ for south,
• ‘E’ for east,
• ‘W’ for west.

Starting from the origin (0, 0), return True if the path crosses itself at any point, i.e., if any point in the path has been visited more than once, and False otherwise.

Example:

• 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: Notice that the path returns to the origin after the second ‘W’.

Clarifying Questions

1. Input Constraints:
   • What is the length of the string path?
   • Constraint: 1 <= path.length <= 10^4
2. Characters in String:
   • Are the directions only ‘N’, ‘S’, ‘E’, and ‘W’?
   • Yes, the directions are guaranteed to be one of these four letters.
3. Output:
   • Should the function return a boolean value?
   • Yes, return True if the path crosses itself, otherwise False.

Strategy

1. Use a Set to Track Visited Locations:
   • We will start from the origin (0, 0).
   • Use a set to store coordinates we visit.
   • As we traverse the string path, we will move according to the direction characters and update our current position.
   • At each move, we check if the new position already exists in the set.
   • If it does, return True; otherwise, continue and add the new position to the set.
   • If we complete the path without revisiting any position, return False.
2. Movement Mapping:
   • Use a dictionary to map each direction to its respective coordinate changes:
     • ‘N’ -> (0, 1)
     • ‘S’ -> (0, -1)
     • ‘E’ -> (1, 0)
     • ‘W’ -> (-1, 0)

Time Complexity

• The time complexity of this approach is O(n), where n is the length of the string path, since we are processing each character exactly once.

Code

def isPathCrossing(path: str) -> bool:
    # Initial position
    x, y = 0, 0
    
    # Set to keep track of visited positions
    visited = set()
    visited.add((x, y))
    
    # Mapping directions to (dx, dy)
    move = {
        'N': (0, 1),
        'S': (0, -1),
        'E': (1, 0),
        'W': (-1, 0)
    }
    
    # Process each step in the path
    for direction in path:
        dx, dy = move[direction]
        x += dx
        y += dy
        if (x, y) in visited:
            return True
        visited.add((x, y))
    
    return False

# Example usages
print(isPathCrossing("NES"))    # Output: False
print(isPathCrossing("NESWW"))  # Output: True

This code will effectively track the path and determine if there is any crossing by checking for repeated coordinates.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?