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'.Problem Overview: You start at coordinate (0,0) on a 2D grid and receive a string of directions containing N, S, E, and W. Each character moves you one step in that direction. The task is to determine whether the path ever visits the same coordinate more than once.
Approach 1: Using a Set to Track Visited Coordinates (O(n) time, O(n) space)
This is the standard and most efficient solution. Maintain the current position using two integers x and y. Start from (0,0) and insert this coordinate into a hash set. As you iterate through the path string, update the coordinates for each move. After each update, check if the coordinate already exists in the set. A hash lookup runs in average O(1) time, so if the position is already present, the path has crossed itself.
The key insight: revisiting a coordinate means the path must intersect or overlap a previously traveled location. A set allows constant-time membership checks, making the algorithm linear relative to the length of the path. This approach relies on a Hash Table to store visited positions and processes the String of directions in a single pass.
Approach 2: Simulate Movement on a 2D Plane (O(n²) time, O(n) space)
This approach also simulates the movement step by step but stores visited coordinates in a list instead of a hash set. After every move, iterate through previously visited coordinates to check if the current position already exists. Because each lookup may scan up to n previous positions, the total time complexity grows to O(n²).
While less efficient, this version helps illustrate the problem mechanics clearly: update coordinates for each direction and verify whether the new position matches any earlier point. It avoids hash-based structures and may be easier to reason about during an initial implementation.
Recommended for interviews: The hash set solution is what interviewers expect. It demonstrates recognition that the problem reduces to detecting duplicate coordinates during traversal. Showing the brute-force simulation first proves you understand the grid movement, but switching to a set for O(n) lookups shows stronger algorithmic thinking and familiarity with hash-based data structures.
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.
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.
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.
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.
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.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), since every character in the path is processed.
Space Complexity: O(n), as we store coordinates in a set.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using a Set to Track Visited Coordinates | 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. |
| Simulate Movement on a 2D Plane | Time Complexity: O(n), since every character in the path is processed. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using a Set to Track Visited Coordinates | O(n) | O(n) | General case. Best approach for interviews and large inputs. |
| Simulate Movement with List Lookup | O(n²) | O(n) | Useful for understanding the movement logic without hash structures. |
Path Crossing - Leetcode 1496 - Python • NeetCodeIO • 14,571 views views
Watch 9 more video solutions →Practice Path Crossing with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor