Path Crossing

Easy
1182.

Path Crossing

Path Crossing is an easy coding problem on strings and hash table, asked in Amazon and Google interviews.

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^4
  • path[i] is either 'N', 'S', 'E' or 'W'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} path
 * @return {boolean}
 */
var isPathCrossing = function(path) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • path[i] is either 'N', 'S', 'E' or 'W'

Hints for Path Crossing

  1. Hint 1

    Track the walker's coordinates as you read the instructions.

  2. Hint 2

    You need to remember every point visited so far, starting with the origin.

  3. 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

  1. Put (0, 0) into an empty set and start at x = y = 0.
  2. For each character, update x or y.
  3. If (x, y) is already in the set, return true; otherwise add it.
  4. 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 False

Java

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