1496. Path Crossing LeetCode Solution

In this guide, you will get 1496. Path Crossing LeetCode Solution with the best time and space complexity. The solution to Path Crossing problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Path Crossing solution in C++
Path Crossing solution in Java
Path Crossing solution in Python
Additional Resources

1496. Path Crossing LeetCode Solution image

Problem Statement of Path Crossing

Given a string path, where path[i] = ‘N’, ‘S’, ‘E’ or ‘W’, each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.
Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.

Example 1:

Input: path = “NES”
Output: false
Explanation: Notice that the path doesn’t cross any point more than once.

Example 2:

Input: path = “NESWW”
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

1 <= path.length <= 104
path[i] is either 'N', 'S', 'E', or 'W'.

Complexity Analysis

Time Complexity:
Space Complexity:

1496. Path Crossing LeetCode Solution in C++

class Solution {
 public:
  bool isPathCrossing(string path) {
    set<int> 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;
  }
};
/* code provided by PROGIEZ */