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.
1#include <unordered_set>
2#include <utility>
3
4class Solution {
5public:
6 bool isPathCrossing(string path) {
7 std::unordered_set<std::pair<int,int>, pair_hash> visited;
8 int x = 0, y = 0;
9 visited.insert({x, y});
10
11 for (char direction : path) {
12 if (direction == 'N') {
13 ++y;
14 } else if (direction == 'S') {
--y;
} else if (direction == 'E') {
++x;
} else if (direction == 'W') {
--x;
}
if (visited.count({x, y})) {
return true;
}
visited.insert({x, y});
}
return false;
}
private:
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1, T2>& pair) const {
auto hash1 = std::hash<T1>{}(pair.first);
auto hash2 = std::hash<T2>{}(pair.second);
return hash1 ^ hash2;
}
};
};This C++ solution uses an unordered_set to track visited coordinates. It includes a custom hash function for a pair of integers since C++ does not provide one by default. Starting at (0, 0), it updates the coordinates for each direction and checks the set to see if the coordinates have been visited. If so, it returns true, else proceeds to 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
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.