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
pathconsisting 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
- Initialize a set to keep track of visited positions.
- Start at the origin (0, 0) and add this position to the set.
- Iterate through each character in the
pathstring:- 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
Trueas we’ve crossed our path. - Otherwise, add the new position to the set.
- If it is, return
- If the loop completes without finding a revisited position, return
False.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the
pathstring. 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
Falseas 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.