Code Implementation

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        visited = set()
        x = y = 0
        visited.add((x, y))
        for move in path:
            if move == 'N':
                y += 1
            elif move == 'S':
                y -= 1
            elif move == 'E':
                x += 1
            elif move == 'W':
                x -= 1
            if (x, y) in visited:
                return True
            visited.add((x, y))
        return False
      

class Solution {
public:
    bool isPathCrossing(string path) {
        set<pair<int, int>> visited;
        int x = 0, y = 0;
        visited.insert({x, y});
        for (char move : path) {
            if (move == 'N') y++;
            else if (move == 'S') y--;
            else if (move == 'E') x++;
            else if (move == 'W') x--;
            if (visited.count({x, y})) return true;
            visited.insert({x, y});
        }
        return false;
    }
};
      

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isPathCrossing(String path) {
        Set<String> visited = new HashSet<>();
        int x = 0, y = 0;
        visited.add(x + "," + y);
        for (char move : path.toCharArray()) {
            if (move == 'N') y++;
            else if (move == 'S') y--;
            else if (move == 'E') x++;
            else if (move == 'W') x--;
            String pos = x + "," + y;
            if (visited.contains(pos)) return true;
            visited.add(pos);
        }
        return false;
    }
}
      

var isPathCrossing = function(path) {
    let visited = new Set();
    let x = 0, y = 0;
    visited.add(`${x},${y}`);
    for (let move of path) {
        if (move === 'N') y++;
        else if (move === 'S') y--;
        else if (move === 'E') x++;
        else if (move === 'W') x--;
        let pos = `${x},${y}`;
        if (visited.has(pos)) return true;
        visited.add(pos);
    }
    return false;
};
      

Problem Description

You are given a string path that consists of the characters 'N', 'S', 'E', and 'W', each representing a move one unit north, south, east, or west on a 2D grid, starting from the origin (0,0).

The task is to determine if the path crosses itself at any point. In other words, does the path ever visit the same point on the grid more than once, including the starting point?

• Each move is exactly one step in the specified direction.
• You must return true if any position is visited more than once, and false otherwise.
• The path may be of any length, and all moves are valid directions.

Thought Process

To solve this problem, we need to track all positions visited as we follow the sequence of moves. The key observation is that the path crosses itself if we ever revisit a position we've already been to.

The brute-force approach would be to store every position we've visited in a list or array, and after each move, check if the new position is already in that list. However, checking for membership in a list is slow for large paths.

To optimize, we can use a set (or a hash set) to store visited positions, since checking whether a position is in a set is much faster (constant time on average). Each position can be represented as a pair of coordinates (x, y).

We start at (0, 0), add it to our set of visited positions, and for each move, update our current coordinates. If the new coordinates are already in the set, we know the path has crossed itself and can return true.

Solution Approach

• Initialization: Start at the origin (0, 0) and add it to a set of visited positions.
• Iterate through the path: For each character in the path string, update the current position according to the move:
  • 'N' increases the y-coordinate by 1.
  • 'S' decreases the y-coordinate by 1.
  • 'E' increases the x-coordinate by 1.
  • 'W' decreases the x-coordinate by 1.
• Check for revisits: After each move, check if the new position is already in the set of visited positions.
• Return result:
  • If the position has been visited, return true immediately (the path crosses itself).
  • If the loop finishes without finding a revisit, return false (no crossing).

We use a set because it allows for O(1) average-time checks and insertions. Each position is stored as a tuple (or a string, depending on the language) to uniquely identify each point on the grid.

Example Walkthrough

Let's walk through an example with path = "NESWW":

1. Start at (0, 0). Visited: {(0, 0)}
2. Move 'N' to (0, 1). Visited: {(0, 0), (0, 1)}
3. Move 'E' to (1, 1). Visited: {(0, 0), (0, 1), (1, 1)}
4. Move 'S' to (1, 0). Visited: {(0, 0), (0, 1), (1, 1), (1, 0)}
5. Move 'W' to (0, 0). (0, 0) is already visited!

At the last step, we return true because the path returns to the starting point, meaning it crosses itself.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n^2), since each new position could be checked against up to n previous positions.
  • Space Complexity: O(n), to store all positions.
• Optimized approach (using a set):
  • Time Complexity: O(n), since each insert and lookup in a set is O(1) on average, and we process each move once.
  • Space Complexity: O(n), since in the worst case we visit n+1 unique positions.

Here, n is the length of the path string.

Summary

The key insight for solving the Path Crossing problem is to efficiently track all visited positions using a set, allowing for quick checks of whether a position has been visited before. By updating coordinates for each move and checking the set, we can determine if the path crosses itself in linear time. This approach is both simple and effective, leveraging hash-based data structures for optimal performance.