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.
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 visits the origin twice.
Constraints:
1 <= path.length <= 104path[i] is either 'N', 'S', 'E', or 'W'.In #1496 Path Crossing, you are given a string representing movements on a 2D grid. Each character moves the position one step north, south, east, or west. The key challenge is determining whether the path ever revisits a previously visited coordinate.
A common and efficient strategy is to simulate the movement step by step while tracking visited coordinates. Starting from the origin (0,0), update the current position based on each move. Store every visited coordinate in a hash set. After each move, check whether the new coordinate already exists in the set. If it does, the path crosses itself.
This approach works well because hash-based lookups are very fast on average. By storing visited positions and checking for duplicates during traversal, we can detect crossings efficiently. The solution processes the path only once, making it suitable for large inputs while keeping the implementation simple.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Simulation with Hash Set of Coordinates | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Simulate the process while keeping track of visited points.
Use a set to store previously visited points.
The idea is to use a Set (or a HashSet in some languages) to store each coordinate visited during the path traversal. Starting from (0, 0), each movement updates the coordinates. If the updated coordinates are already in the Set, it means that the path has crossed itself, and we return true. Otherwise, continue until the end of the path and return false.
Time Complexity: O(n), where n is the length of the path, as we iterate through the path once, with O(1) operations for each set lookup.
Space Complexity: O(n), as we store up to n coordinates in the set.
1def isPathCrossing(path):
2 visited = set()
3 x, y = 0, 0
4 visited.add((x, y))
This Python solution initializes a set for visited coordinates, and starts at the origin (0, 0). It then iterates over the path, updating the x and y coordinates based on the direction. The coordinate (x, y) is checked against the set to see if it already exists. If it does, the path has crossed itself, and the function returns True. Otherwise, it continues until the end, returning False.
In this approach, we simulate movement on a 2D plane. Starting at the origin (0, 0), the path string is processed character by character to update the current position based on the direction: 'N' increases y, 'S' decreases y, 'E' increases x, and 'W' decreases x. A map or set records visits to each unique position. If a position is visited more than once, the path crosses itself.
Time Complexity: O(n), since every character in the path is processed.
Space Complexity: O(n), as we store coordinates in a set.
1def isPathCrossing
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like Path Crossing are common in technical interviews because they test understanding of hash sets, coordinate simulation, and string traversal. Variations of grid traversal and visited-state tracking frequently appear in FAANG-style interview questions.
Tracking coordinates helps determine whether the path revisits a location. By updating the current position after each movement and storing it, we can immediately detect if the same position occurs again.
The optimal approach is to simulate the movement on a 2D grid and store every visited coordinate in a hash set. If a coordinate appears again during traversal, the path crosses itself. This method works in linear time with efficient constant-time lookups.
A hash set is the best data structure because it allows quick checks to see whether a coordinate has already been visited. Each position can be stored as a pair of coordinates, making duplicate detection straightforward.
In this Python function, a set keeps track of each position visited as (x, y) tuples. Starting at (0, 0), we iterate through the path, adjusting coordinates for each direction and checking against the set to detect crossings.