Path Crossing — Solution in Python, Java & C++
Path Crossing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.
Path Crossing is an easy coding problem on strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A walker starts at the origin (0, 0) of a grid and follows the instructions in path, one character per step: 'N' moves one unit north (y + 1), 'S' one unit south (y - 1), 'E' one unit east (x + 1) and 'W' one unit west (x - 1).
Return true if the walker ever stands on a point it has already visited — the origin counts as visited from the start — and false otherwise.
Example 1
Input: path = "NNEE"
Output: false
Example 2
Input: path = "NEWS"
Output: true
Explanation: After `N` and `E` the walker is at (1,1); `W` brings it back to (0,1).
Example 3
Input: path = "EESWWN"
Output: true
Explanation: The last step returns to the origin.
Constraints
1 <= path.length <= 10^4path[i] is either 'N', 'S', 'E' or 'W'
Hints for Path Crossing
Hint 1
Track the walker's coordinates as you read the instructions.
Hint 2
You need to remember every point visited so far, starting with the origin.
Hint 3
Store the points in a hash set (encode a point as one number or a string); the first time a new position is already in the set, answer true.
How to solve Path Crossing
Simulate the walk and keep every visited point in a hash set; a crossing is simply a position that is already in the set.
Approach
- Put
(0, 0)into an empty set and start atx = y = 0. - For each character, update
xory. - If
(x, y)is already in the set, returntrue; otherwise add it. - If the walk ends without a repeat, return
false.
Why it works
The set holds exactly the points visited before the current step, so the check answers "has this point been visited already" at every step. Encoding a point as a single integer such as (x + 10001) * 20003 + (y + 10001) is collision-free because both coordinates stay within ±10^4.
Complexity
- Time —
O(n) expected - Space —
O(n)
Pitfalls
- The origin is visited before the first move —
"NS"crosses. - Encoding a point as
x * 10 + y(or concatenating digits without a separator) makes different points collide. - Checking only for a return to the origin misses crossings elsewhere.
Reference solution
Python
def isPathCrossing(path: str) -> bool:
moves = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
x = y = 0
seen = {(0, 0)}
for c in path:
dx, dy = moves[c]
x += dx
y += dy
if (x, y) in seen:
return True
seen.add((x, y))
return FalseJava
public static boolean isPathCrossing(String path) {
Set<Integer> seen = new HashSet<>();
int x = 0, y = 0;
seen.add(10001 * 20003 + 10001);
for (int i = 0; i < path.length(); i++) {
char c = path.charAt(i);
if (c == 'N') y++;
else if (c == 'S') y--;
else if (c == 'E') x++;
else x--;
if (!seen.add((x + 10001) * 20003 + (y + 10001))) return true;
}
return false;
}C++
bool isPathCrossing(string path) {
set<pair<int, int>> seen;
int x = 0, y = 0;
seen.insert({0, 0});
for (char c : path) {
if (c == 'N') y++;
else if (c == 'S') y--;
else if (c == 'E') x++;
else x--;
if (!seen.insert({x, y}).second) return true;
}
return false;
}JavaScript
var isPathCrossing = function(path) {
var x = 0, y = 0;
var seen = new Set(["0,0"]);
for (var i = 0; i < path.length; i++) {
var c = path[i];
if (c === "N") y++;
else if (c === "S") y--;
else if (c === "E") x++;
else x--;
var key = x + "," + y;
if (seen.has(key)) return true;
seen.add(key);
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets