< Back

1496. Path Crossing

Pretty straightforward, just requires a little extra work in setting up the processing of the input.
We're asked to detemine if a path specification from an input string ends up causing us to cross
paths on a 2D plane. We're given instructions to use NSEW as our directions, correlating to up, down,
left, and right.

Best and easiest way to solve this is to start at the origin (0, 0), adding this tuple to set since
tuples are hashable. Then we iterate through the path string, keeping track of our current location.
If the updated location after taking instructions from the path causes us to return to a location
previously visited, we return True - we crossed our own path. Otherwise, we add the current location
to the visited set.

We continue to do this until we iterate through the entire path. Then we return False.

The solution is as follows:

  class Solution:
      def isPathCrossing(self, path: str) -> bool:
          curr = [0, 0]
          visited = set()

          for direction in path:
              if direction == "N": curr[1] += 1
              elif direction == "S": curr[1] -= 1
              elif direction == "E": curr[0] += 1
              elif direction == "W": curr[0] -= 1
              if tuple(curr) in visited: return True

          return False

_ Time Complexity:

  O(n) - We iterate through the path string once, where n is the length of the path string.

_ Space Complexity:

  O(n) - We store the visited locations in a set, where n is the length of the path string.