Path Crossing - Leetcode Solution

Problem statement:

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, otherwise, return False.

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 <= 10^4

Solution:

We can solve this problem by keeping track of the current position of the walker on the 2D plane. We will iterate over the characters in the path and move the walker according to the character. If the walker crosses its own path, we will return True. Otherwise, we will return False.

We can keep track of the walker's position using two variables, x and y. Initially, x = y = 0, as the walker starts at the origin. We will also maintain a set of visited positions. At each step, we will check if the current position of the walker is already in the visited set. If it is, we will return True as the path has crossed itself. Otherwise, we will add the current position to the visited set.

Let's take an example to understand the solution.

Example: path = "NESWW"

Initially, x = y = 0.

For the first character, 'N', we move the walker one unit north, i.e., y += 1. The current position of the walker is (0, 1), which we add to the visited set.

For the second character, 'E', we move the walker one unit east, i.e., x += 1. The current position of the walker is (1, 1), which we add to the visited set.

For the third character, 'S', we move the walker one unit south, i.e., y -= 1. The current position of the walker is (1, 0), which we add to the visited set.

For the fourth character, 'W', we move the walker one unit west, i.e., x -= 1. The current position of the walker is (0, 0), which we add to the visited set.

For the fifth character, 'W', we move the walker one unit west, i.e., x -= 1. The current position of the walker is (-1, 0), which we add to the visited set.

Now, we have visited the origin twice, which means that the path has crossed itself. So, we return True.

Let's see the Python implementation of the solution.

Python code:

class Solution: def isPathCrossing(self, path: str) -> bool: x = y = 0 visited = {(0, 0)} for step in path: if step == 'N': y += 1 elif step == 'S': y -= 1 elif step == 'E': x += 1 else: x -= 1 if (x, y) in visited: return True visited.add((x, y)) return False

Time Complexity: O(n) Space Complexity: O(n)

In this solution, we are iterating over the characters in the path, which takes O(n) time. We are also maintaining a set of visited positions, which can have up to O(n) elements in the worst case. Therefore, the space complexity of the solution is also O(n).

This solution gets accepted on LeetCode.

1