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.
1function isPathCrossing(path) {
2 const visited = new Set();
3 let x = 0, y = 0;
4 visited.
This JavaScript function employs a Set to store visited x,y coordinate strings. We start at (0, 0), update coordinates according to each path direction, and check for visited coordinates in the set. If revisited, it returns true; otherwise, it completes the loop and returns 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.
1using System;
2using System.Collections.Generic;
public class Solution {
public bool IsPathCrossing(string path) {
var visited = new HashSet<(int, int)>();
int x = 0, y = 0;
visited.Add((x, y));
foreach (char direction in path) {
if (direction == 'N') {
y++;
} else if (direction == 'S') {
y--;
} else if (direction == 'E') {
x++;
} else if (direction == 'W') {
x--;
}
var current = (x, y);
if (visited.Contains(current)) {
return true;
}
visited.Add(current);
}
return false;
}
}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.
C# solution leverages a HashSet for tracking coordinates using tuple structures, adjusting position per direction and verifying if any are revisited.