Leetcode 1496. Path Crossing

Problem Explanation

The problem aims at finding if a given 'walk' path crosses itself at any point. The path is given as a string where each character represents a move in one of the four cardinal directions: North 'N', South 'S', East 'E', or West 'W'. We start at a coordinate point (0, 0) and follow the moves defined in the path. If at any point we revisit a coordinate that we have visited before, then we say that the 'walk' path crosses itself and we return true, otherwise we return false.

Let's consider an instance: Let's say our path string is "NESWW". Here:

• Initially, we start at (0, 0)
• Move North 'N' to (0, 1)
• Move East 'E' to (1, 1)
• Move South 'S' to (1, 0)
• Move West 'W' to (0, 0), this is a place we've visited before
• Move West 'W' to (-1, 0)

At the 4th step, we revisit a coordinate we had been to previously. In this case, we would return true.

Approach

Given the problem constraints, we can map this problem into a 2D plane problem in which every unique point on the 2D plane can be represented uniquely as an integer by using Cantor's pairing function.

This function can be represented as:

p1 * length + p2 * where p1 and p2 are coordinates.

This unique number could then be stored as visited cells. In our case, we use the distance of 20001 from the origin in all directions as the maximum reachable distance which is a reasonable estimate (any number greater than path length could have been used). With this, every unique (p1, p2) pair will map to a unique integer.

If at any point during the walk we find the unique coordinate already in the list of visited coordinates, this means we have crossed our path and we can return True.

Python Solution

1
2python
3class Solution:
4    def isPathCrossing(self, path: str) -> bool:
5        steps = [(0, 0)]
6        x, y = 0, 0
7        for move in path:
8            if move == 'N':
9                y += 1
10            elif move == 'W':
11                x -= 1
12            elif move == 'S':
13                y -= 1
14            elif move == 'E':
15                x += 1
16            if (x, y) in steps:
17                return True
18            else:
19                steps.append((x, y))
20        return False

Java Solution

1
2java
3class Solution {
4    public boolean isPathCrossing(String path) {
5        Set<Pair<Integer, Integer>> visited = new HashSet<>();
6        int x = 0, y = 0;
7        
8        visited.add(new Pair<>(0, 0)); 
9        for (char move : path.toCharArray()) {
10            if (move == 'N') y++;
11            if (move == 'S')  y--;
12            if (move == 'E')  x++;
13            if (move == 'W') x--;
14            Pair<Integer, Integer> next = new Pair<>(x, y);
15            if (!visited.add(next)) {
16                return true;
17            }
18        }
19        
20        return false;
21    }
22}

Javascript Solution

1
2javascript
3var isPathCrossing = function(path) {
4    let visited = new Set(['0,0']);
5    let x = 0;
6    let y = 0;
7    
8    for (let move of path) {
9        if (move === 'N') y++;
10        if (move === 'S') y--;
11        if (move === 'E') x++;
12        if (move === 'W') x--;
13        
14        const pos = `${x},${y}`;
15        
16        if (visited.has(pos)) {
17            return true;
18        }
19        
20        visited.add(pos);
21    }
22    
23    return false;
24};

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isPathCrossing(string path) {
6        set<pair<int, int>> s;
7        s.insert({0, 0});
8        int x = 0, y = 0;
9        for (char move: path) {
10            if (move == 'N') y++;
11            if (move == 'S') y--;
12            if (move == 'E') x++;
13            if (move == 'W') x--;
14            pair<int, int> next = {x, y};
15            if (s.find(next) != s.end()) {
16                return true;
17            }
18            s.insert(next);
19        }
20        
21        return false;
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsPathCrossing(string path) {
5        var visited = new HashSet<string>();
6        visited.Add("0,0");
7        int x = 0, y= 0;
8        foreach (char move in path) {
9            if (move == 'N') y++;
10            if (move == 'S') y--;
11            if (move == 'E') x++;
12            if (move == 'W') x--;
13            var pos = $"{x},{y}";
14            if (visited.Contains(pos)) {
15                return true;
16            }
17            visited.Add(pos);
18        }
19        
20        return false;
21    }
22}

Within each solution, we iterate through each movement on the path and update our coordinates accordingly. We then check if the new coordinate is already in our set of visited coordinates. If so, then we return True as we have revisited a coordinate, therefore, the path crosses itself.If we manage to complete all moves without revisiting any coordinates, then the path does not cross itself, and the function returns False.

In all five solutions, we use a set or list to track visited coordinates. A set in Python, JavaScript, C++, C#, or a HashSet in Java provides constant time complexity O(1) for insertion and retrieval, making it an ideal data structure for this problem.

Time Complexity

The time complexity of this problem is O(n), where n is the number of characters in the path string. This is because we iterate through the path string only once in a for loop.

Space Complexity

The space complexity of this problem is also O(n), where n is the number of characters in the path string. This is due to the fact that in the worst-case scenario, we would have to store each unique coordinate pair inside the set.

It is essential to note that in our solutions, we're using a grid of maximum size which is far bigger than the path length, in order to avoid collisions in the Cantor pairing function but since the size of the path determines the number of moves, the space complexity can still be considered linear in the size of the path.

The approaches we've demonstrated in Python, JavaScript, Java, C#, and C++ will efficiently solve the problem of determining whether a walk path will cross itself by storing visited coordinates in a HashSet or list and checking for any revisited coordinates, however, it can be further optimized by directly using Cantor pairing function to map the coordinates to a unique integer and then storing and checking these integers.

Remember that understanding the problem expressly and thinking of a feasible solution is key to solving any programming problem efficiently. Do not forget to write clean code and test your code on different sample inputs. Happy coding!