Path Crossing

How it works

Instead of storing coordinates as strings or tuples, we can encode them into a single integer. By shifting one coordinate (e.g., x << 32) and adding the other, we create a unique hash for each position. This can improve performance by avoiding string concatenation overhead.

Steps

1. Define a hash function: hash(x, y) = (x << 32) + y.
2. Initialize a set and add hash(0, 0).
3. Track position with x = 0, y = 0.
4. For each character in the path:
   • Update coordinates based on direction.
   • Compute the hash of the new position.
   • If it exists in the set, return true.
   • Otherwise, add the hash to the set.
5. Return false if no crossing is found.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Forgetting to Add the Starting Position

A common mistake is forgetting to add the origin (0, 0) to the visited set before processing the path. The path can cross the starting point, so it must be tracked from the beginning. If you only add positions after moving, you will miss cases where the path returns to the origin.

Incorrect Coordinate Representation

When storing coordinates in a hash set, using improper representations can cause collisions or misses. For example, concatenating coordinates as x + y instead of x + "," + y can produce identical strings for different coordinate pairs (e.g., (1, 23) and (12, 3) both become "123"). Always use a delimiter or tuple representation to ensure uniqueness.

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        visit = set()
        x, y = 0, 0
        visit.add(self.hash(x, y))

        for c in path:
            if c == 'N':
                y += 1
            elif c == 'S':
                y -= 1
            elif c == 'E':
                x += 1
            elif c == 'W':
                x -= 1

            pos = self.hash(x, y)
            if pos in visit:
                return True
            visit.add(pos)

        return False

    def hash(self, x: int, y: int) -> int:
        return (x << 32) + y

class Solution {
public:
    bool isPathCrossing(string path) {
        unordered_set<pair<int, int>, pair_hash> visit;
        int x = 0, y = 0;
        visit.insert({x, y});

        for (char c : path) {
            if (c == 'N') y++;
            else if (c == 'S') y--;
            else if (c == 'E') x++;
            else if (c == 'W') x--;

            if (visit.count({x, y})) return true;
            visit.insert({x, y});
        }

        return false;
    }

private:
    struct pair_hash {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2>& p) const {
            return (hash<T1>()(p.first) << 32) + hash<T2>()(p.second);
        }
    };
};