Path Crossing - Leetcode 1496 - Python
Path Crossing - Video Solution
Watch 10 video solutions for Path Crossing, a easy level problem involving Hash Table, String. This walkthrough by NeetCodeIO has 14,757 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text 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, that is, if at any time you are on a location you have previously visited. Return false otherwise.
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 <= 104path[i]is either'N','S','E', or'W'.
Approach Overview
Problem Overview: You start at coordinate (0,0) on a 2D grid and receive a string of directions containing N, S, E, and W. Each character moves you one step in that direction. The task is to determine whether the path ever visits the same coordinate more than once.
Approach 1: Using a Set to Track Visited Coordinates (O(n) time, O(n) space)
This is the standard and most efficient solution. Maintain the current position using two integers x and y. Start from (0,0) and insert this coordinate into a hash set. As you iterate through the path string, update the coordinates for each move. After each update, check if the coordinate already exists in the set. A hash lookup runs in average O(1) time, so if the position is already present, the path has crossed itself.
The key insight: revisiting a coordinate means the path must intersect or overlap a previously traveled location. A set allows constant-time membership checks, making the algorithm linear relative to the length of the path. This approach relies on a Hash Table to store visited positions and processes the String of directions in a single pass.
Approach 2: Simulate Movement on a 2D Plane (O(nĀ²) time, O(n) space)
This approach also simulates the movement step by step but stores visited coordinates in a list instead of a hash set. After every move, iterate through previously visited coordinates to check if the current position already exists. Because each lookup may scan up to n previous positions, the total time complexity grows to O(nĀ²).
While less efficient, this version helps illustrate the problem mechanics clearly: update coordinates for each direction and verify whether the new position matches any earlier point. It avoids hash-based structures and may be easier to reason about during an initial implementation.
Recommended for interviews: The hash set solution is what interviewers expect. It demonstrates recognition that the problem reduces to detecting duplicate coordinates during traversal. Showing the brute-force simulation first proves you understand the grid movement, but switching to a set for O(n) lookups shows stronger algorithmic thinking and familiarity with hash-based data structures.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using a Set to Track Visited Coordinates | O(n) | O(n) | General case. Best approach for interviews and large inputs. |
| Simulate Movement with List Lookup | O(nĀ²) | O(n) | Useful for understanding the movement logic without hash structures. |