Path Crossing Solution in C++

Problem Description

Imagine you’re on a leisurely stroll, trying to navigate through a park, but instead of enjoying the scenery, you keep bumping into yourself. Yes, that’s right! The “Path Crossing” problem is all about figuring out if your path crosses itself while you’re wandering around.

In this delightful little challenge, you’re given a string representing directions: ‘N’ for North, ‘S’ for South, ‘E’ for East, and ‘W’ for West. Your task is to determine if you ever end up at the same spot twice. It’s like trying to find your way out of a maze, only to realize you’ve been going in circles the whole time.

So, if you think you can navigate without retracing your steps, think again!

Code Solution

Here’s the C++ solution that will help you avoid those pesky self-collisions:


class Solution {
 public:
  bool isPathCrossing(string path) {
    set seen;

    seen.insert(0);

    int x = 0;
    int y = 0;

    for (const char c : path) {
      switch (c) {
        case 'N':
          ++y;
          break;
        case 'S':
          --y;
          break;
        case 'E':
          ++x;
          break;
        case 'W':
          --x;
          break;
      }
      const int key = x * 20001 + y;
      if (seen.contains(key))
        return true;
      seen.insert(key);
    }

    return false;
  }
};

Approach

The approach taken in this solution is straightforward yet effective. We maintain a set to keep track of all the positions we’ve visited. As we iterate through the path string, we update our current coordinates based on the direction indicated by each character. After updating our position, we check if we’ve already visited that position by looking it up in the set. If we have, it means we’ve crossed our path, and we return true. If we finish the loop without finding any duplicates, we return false.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the path string.
Space Complexity	O(n), in the worst case, where we store all unique positions in the set.

Real-World Example

Think of it like trying to navigate through a crowded mall. You start at the entrance and decide to explore. You go North to the food court, then South to the electronics store, East to the clothing section, and West back to the entrance. If you find yourself back at the food court after just a few minutes, you’ve crossed your path! This problem is all about ensuring you don’t end up in the same spot twice while trying to enjoy your shopping spree.