LeetCode 1496 - Path Crossing

LeetCode Problem 1496

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

This problem asks us to simulate movement on a 2D plane according to a string of directional instructions. Each character in the string represents a move of one unit in a cardinal direction: 'N' for north (up), 'S' for south (down), 'E' for east (right), and 'W' for west (left). You always start at the origin (0, 0) and follow the path step by step. The task is to determine whether at any point you revisit a location you have already been to. If you do, the function should return true; otherwise, it should return false.

The input is a string with length between 1 and 10,000, so any solution must handle potentially long paths efficiently. Edge cases include very short paths (length 1), paths that immediately return to the origin, and paths that traverse large areas without intersecting.

Key points: the movement is discrete on integer coordinates, revisiting a point anywhere in the path counts as crossing, and there are no diagonal moves. The problem guarantees valid input characters, so no input validation is necessary.

Approaches

A brute-force approach would involve storing all visited coordinates in a list and checking at each step whether the new position already exists in that list. While correct, this requires scanning the list for each move, which leads to O(n²) time complexity for n steps, which is too slow for n up to 10,000.

The key observation for an optimal solution is that a hash-based structure allows O(1) membership checks. By storing visited coordinates in a hash set, we can check for revisits immediately at each step, resulting in an O(n) solution in both time and space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Stores coordinates in a list and checks membership linearly
Optimal	O(n)	O(n)	Uses a hash set to store visited coordinates for constant-time checks

Algorithm Walkthrough

1. Initialize a hash set to store visited coordinates. Start by adding (0, 0) since that is the starting point.

2. Set two variables x and y to represent the current position, initially (0, 0).

3. Iterate over each character in the path string:

4. Update x or y according to the direction: 'N' increments y, 'S' decrements y, 'E' increments x, 'W' decrements x.

5. Form a tuple (x, y) for the new position.

6. Check if this tuple already exists in the hash set of visited positions.

• If it does, immediately return true.
• Otherwise, add the tuple to the hash set.

4. If the loop completes without finding a duplicate, return false.

Why it works: The algorithm maintains an invariant that the set always contains all locations visited so far. By checking membership at each step, it ensures that any repeated position is detected immediately.

Python Solution

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

The Python implementation follows the algorithm exactly. It uses a set to store visited coordinates, updates the (x, y) position according to each move, checks for revisits, and returns the correct boolean. Using tuples as keys in the set ensures fast lookups.

Go Solution

func isPathCrossing(path string) bool {
    visited := make(map[[2]int]bool)
    x, y := 0, 0
    visited[[2]int{x, y}] = true
    
    for _, move := range path {
        switch move {
        case 'N':
            y++
        case 'S':
            y--
        case 'E':
            x++
        case 'W':
            x--
        }
        
        pos := [2]int{x, y}
        if visited[pos] {
            return true
        }
        visited[pos] = true
    }
    
    return false
}

In Go, a map with array keys is used for visited coordinates. Go arrays are comparable, making them valid map keys. The implementation mirrors the Python version with a switch statement for direction updates.

Worked Examples

Example 1: path = "NES"

Step	Move	x	y	Visited Positions	Crossed?
0	Start	0	0	{(0,0)}	No
1	N	0	1	{(0,0),(0,1)}	No
2	E	1	1	{(0,0),(0,1),(1,1)}	No
3	S	1	0	{(0,0),(0,1),(1,1),(1,0)}	No

Returns false.

Example 2: path = "NESWW"

Step	Move	x	y	Visited Positions	Crossed?
0	Start	0	0	{(0,0)}	No
1	N	0	1	{(0,0),(0,1)}	No
2	E	1	1	{(0,0),(0,1),(1,1)}	No
3	S	1	0	{(0,0),(0,1),(1,1),(1,0)}	No
4	W	0	0	{(0,0),(0,1),(1,1),(1,0)}	Yes

Returns true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each move is processed once, with constant-time hash set operations
Space	O(n)	Stores up to n+1 unique coordinates in the visited set

Even for the maximum path length of 10,000, this algorithm is efficient and avoids unnecessary nested loops.

Test Cases

# Provided examples
assert Solution().isPathCrossing("NES") == False  # No crossing
assert Solution().isPathCrossing("NESWW") == True  # Crosses at origin

# Edge cases
assert Solution().isPathCrossing("N") == False  # Single move, cannot cross
assert Solution().isPathCrossing("NS") == True  # Returns to origin immediately
assert Solution().isPathCrossing("EEWW") == True  # Horizontal crossing
assert Solution().isPathCrossing("NNNSSS") == True  # Vertical crossing
assert Solution().isPathCrossing("NESWNESW") == True  # Multiple crossings
assert Solution().isPathCrossing("N"*10000) == False  # Long straight line, no crossing

Test	Why
"NES"	Simple path with no crossing
"NESWW"	Crosses origin
"N"	Minimum input length, cannot cross
"NS"	Immediate return to start
"EEWW"	Horizontal loop
"NNNSSS"	Vertical loop
"NESWNESW"	Multiple crossings, verifies hash set handling
"N"*10000	Long path, stress test for time/space

Edge Cases

The first important edge case is a path that immediately returns to the origin, such as "NS". A naive implementation might forget to mark (0, 0) as visited initially, causing it to miss the crossing. Our implementation adds the origin to the visited set before the loop.

The second edge case is a path consisting of a single repeated direction for a long distance, like "N"*10000. This tests that the algorithm does not falsely report crossings when none exist and that it scales efficiently to the maximum input length.

The third edge case is a path that forms a loop in one dimension before completing another dimension, for example "EEWW". Some implementations that only track the last position could incorrectly conclude there is no crossing, but our solution keeps all visited positions in a hash set, ensuring correctness.