1496. Path Crossing - Explanation

Problem Link



1. Hash Set

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        dir = {
            'N': [0, 1],
            'S': [0, -1],
            'E': [1, 0],
            'W': [-1, 0]
        }

        visit = set()
        x, y = 0, 0

        for c in path:
            visit.add((x, y))
            dx, dy = dir[c]
            x, y = x + dx, y + dy
            if (x, y) in visit:
                return True

        return False

Time & Space Complexity

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

2. Hash Set (Custom Hash)

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

Time & Space Complexity

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