#1496

Easy

LeetCode Problem Workspace

Path Crossing

Check if a path crosses itself on a 2D plane using a hash table to track visited points during traversal.

Problem Statement

You are given a string path consisting of characters 'N', 'S', 'E', and 'W'. These characters represent moving one unit north, south, east, or west on a 2D plane, starting from the origin (0, 0). Your task is to determine if the path crosses itself at any point, meaning if you visit the same location more than once during the walk.

Return true if the path crosses itself at any point, otherwise return false. For example, in the path NESWW, the walk crosses itself since it visits the origin twice.

Examples

Example 1

Input: path = "NES"

Output: false

Notice that the path doesn't cross any point more than once.

Example 2

Input: path = "NESWW"

Output: true

Notice that the path visits the origin twice.

Constraints

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

Solution Approach

Simulate the Path

Simulate walking through each direction in the path. Start at (0, 0) and update the current position based on the current direction (N, S, E, W).

Track Visited Locations with Hash Table

Use a hash table to store all visited coordinates. Before moving to a new location, check if the location has been visited before. If it has, return true, indicating the path crosses itself.

Efficiently Check for Repeated Points

Using a hash table allows for efficient O(1) time complexity when checking if a location has been visited before. This ensures that the algorithm runs in linear time, O(n), where n is the length of the path.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because we iterate through each character in the path once, and each hash table operation (insert and lookup) takes O(1) time. The space complexity is O(n) due to the storage required for the hash table to track visited points.

What Interviewers Usually Probe

Ability to recognize the importance of hashing for tracking visited points in path problems.
Effective use of hash tables for fast lookups to detect repeated points.
Clear understanding of the simulation pattern and its relation to path traversal problems.

Common Pitfalls or Variants

Common pitfalls

Failing to track the starting point (0, 0) as a visited location can lead to incorrect results.
Using inefficient data structures like arrays instead of hash tables, leading to slower performance for large inputs.
Not handling edge cases like very short paths (e.g., paths of length 1) or paths with only one direction.

Follow-up variants

What if the path involves diagonal moves, not just N, S, E, W?
How would the solution change if the plane was 3D instead of 2D?
What if the path has obstacles that block movement, and you need to account for those?

FAQ

What is the time complexity of the Path Crossing problem?

The time complexity is O(n), where n is the length of the path, as we visit each location once and check for revisits in constant time using a hash table.

What is the space complexity of the Path Crossing problem?

The space complexity is O(n), due to the need to store the visited points in a hash table.

How can I optimize the Path Crossing solution?

Using a hash table to store visited points ensures that the solution is both time and space efficient, with constant-time lookups and updates.

What are common mistakes when solving the Path Crossing problem?

Common mistakes include forgetting to track the starting point or using inefficient data structures like arrays for storing visited points.

What is the key pattern to solving the Path Crossing problem?

The key pattern is to simulate the path while tracking visited points using a hash table to efficiently check for path crossings.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#1487 making file names unique #1525 number of good ways to split a string #1461 check if a string contains all binary codes of size k