# Path Crossing
**Difficulty:** EASY
[External](https://leetcode.com/problems/path-crossing)
Canonical: https://scaleengineer.com/dsa/problems/path-crossing
**Data structures:** Hash Table, String
**Companies:** [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
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:**

![](https://assets.glich.co/dsa/path-crossing/image0.png) 

**Input:** path = "NES"
**Output:** false 
**Explanation:** Notice that the path doesn't cross any point more than once.

**Example 2:**

![](https://assets.glich.co/dsa/path-crossing/image1.png) 

**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'`.

# Approaches
## Brute Force with List
This approach simulates the path step by step and keeps track of all visited coordinates in a list. For each new coordinate, it iterates through the entire list of previously visited coordinates to check for a match.
**Time:** O(N^2), where N is the length of the path. For each of the N steps, we may have to scan up to N previous points in the list. The total number of comparisons is roughly the sum of integers from 1 to N, which is O(N^2). · **Space:** O(N), where N is the length of the path. In the worst-case scenario (when the path never crosses), we store all N+1 visited points in the list.
**Pros:** Simple to understand and implement.; Doesn't require complex data structures beyond a basic list.
**Cons:** Inefficient for long paths due to the nested loop structure, leading to a quadratic time complexity.; Can be slow and may result in a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
The brute-force method involves a straightforward simulation of the walk. We maintain the current `(x, y)` coordinates, starting from the origin `(0, 0)`. We use a dynamic list (like an `ArrayList` in Java) to store the history of all visited coordinates. The starting point `(0, 0)` is the first entry in our list. Then, for each move in the given path, we update our current coordinates. After each move, we perform a linear scan through our list of visited points to see if the new coordinate has been visited before. If it has, we've found a crossing and can immediately return `true`. Otherwise, we add the new coordinate to our list and proceed to the next move. If we process the entire path without finding any crossings, we return `false`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isPathCrossing(String path) {
        List<int[]> visitedPoints = new ArrayList<>();
        int x = 0, y = 0;
        visitedPoints.add(new int[]{0, 0});

        for (char move : path.toCharArray()) {
            if (move == 'N') y++;
            else if (move == 'S') y--;
            else if (move == 'E') x++;
            else if (move == 'W') x--;

            for (int[] point : visitedPoints) {
                if (point[0] == x && point[1] == y) {
                    return true;
                }
            }
            visitedPoints.add(new int[]{x, y});
        }
        return false;
    }
}
```
### Algorithm
- Initialize current coordinates `x = 0`, `y = 0`.
- Create a list of integer arrays, `visitedPoints`, to store the coordinates of each point visited.
- Add the starting point `{0, 0}` to `visitedPoints`.
- Iterate through each character `move` in the input `path` string.
- Update `x` and `y` according to the direction specified by `move`.
- After updating the coordinates, iterate through the `visitedPoints` list.
- For each `point` in the list, check if its coordinates match the current `(x, y)`.
- If a match is found, it means the path has crossed itself, so return `true`.
- If no match is found after checking all previous points, add the current `{x, y}` to `visitedPoints`.
- If the loop completes without finding any crossing, return `false`.

## Optimized Approach using a HashSet
This approach improves upon the brute-force method by using a `HashSet` to store visited coordinates. A `HashSet` provides average O(1) time complexity for lookups, which significantly speeds up the process of checking if a coordinate has been visited before.
**Time:** O(N), where N is the length of the path. We iterate through the path once. Each operation inside the loop (coordinate update, string creation, and HashSet insertion/lookup) takes, on average, constant time, O(1). · **Space:** O(N), where N is the length of the path. In the worst case, if the path never crosses, the `HashSet` will store N+1 unique coordinate strings.
**Pros:** Highly efficient with a linear time complexity of O(N).; This is the optimal solution for the given constraints.
**Cons:** Requires extra space for the HashSet.; Incurs a small overhead from string creation and hashing, though this is generally negligible.
### Explanation
To optimize the check for previously visited points, we can replace the list with a `HashSet`. A `HashSet` allows for checking the existence of an element in average constant time, O(1). The overall algorithm remains similar: we traverse the path and update our coordinates. However, instead of a linear scan, we use the `HashSet` to check for previous visits. To store a 2D coordinate pair `(x, y)` in the set, we need a hashable representation. A simple and effective way is to convert the pair into a unique string, such as `"x,y"`. We start by adding the origin `"0,0"` to the set. For each move, we update `(x, y)`, create the corresponding string key, and try to add it to the set. If the `add` operation fails (because the key is already in the set), we have found a crossing and return `true`. Otherwise, the new key is added, and we continue. If we traverse the entire path, we return `false`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isPathCrossing(String path) {
        Set<String> visited = new HashSet<>();
        int x = 0, y = 0;
        visited.add("0,0");

        for (char move : path.toCharArray()) {
            if (move == 'N') y++;
            else if (move == 'S') y--;
            else if (move == 'E') x++;
            else if (move == 'W') x--;

            String currentPos = x + "," + y;
            if (!visited.add(currentPos)) {
                // add() returns false if the element is already in the set
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize current coordinates `x = 0`, `y = 0`.
- Create a `HashSet` of strings, `visited`, to store unique visited coordinates.
- To store a coordinate pair `(x, y)` in the set, convert it to a unique string format, e.g., `"x,y"`.
- Add the string representation of the starting point, `"0,0"`, to the `visited` set.
- Iterate through each character `move` in the `path` string.
- Update `x` and `y` based on the `move`.
- Create the string key for the new coordinate.
- Attempt to add the key to the `visited` set. The `add` method returns `false` if the key is already present.
- If `add` returns `false`, a crossing has occurred, so return `true`.
- If the loop finishes, it means no point was revisited, so return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPathCrossing(String path) {
    int i = 0, j = 0;
    Set<Integer> vis = new HashSet<>();
    vis.add(0);
    for (int k = 0, n = path.length(); k < n; ++k) {
      switch (path.charAt(k)) { case 'N' -> -- i ; case 'S' -> ++ i ; case 'E' -> ++ j ; case 'W' -> -- j ; } int t = i * 20000 + j ; if (! vis . add ( t )) { return true ; } } return false ; } }

```

### CPP

```cpp
class Solution {
public:
  bool isPathCrossing(string path) {
    int i = 0, j = 0;
    unordered_set<int> s{{0}};
    for (char &c : path) {
      if (c == 'N') {
        --i;
      } else if (c == 'S') {
        ++i;
      } else if (c == 'E') {
        ++j;
      } else {
        --j;
      }
      int t = i * 20000 + j;
      if (s.count(t)) {
        return true;
      }
      s.insert(t);
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def isPathCrossing(self, path: str) -> bool: i = j = 0 vis = {(0, 0)} for c in path: match c: case 'N': i -= 1 case 'S': i += 1 case 'E': j += 1 case 'W': j -= 1 if (i, j) in vis: return True vis . add((i, j)) return False

```