Path Crossing - Solution & Explanation
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.
Approach 1: Using a Set to Track Visited Coordinates
The idea is to use a Set (or a HashSet in some languages) to store each coordinate visited during the path traversal. Starting from (0, 0), each movement updates the coordinates. If the updated coordinates are already in the Set, it means that the path has crossed itself, and we return true. Otherwise, continue until the end of the path and return false.
This Python solution initializes a set for visited coordinates, and starts at the origin (0, 0). It then iterates over the path, updating the x and y coordinates based on the direction. The coordinate (x, y) is checked against the set to see if it already exists. If it does, the path has crossed itself, and the function returns True. Otherwise, it continues until the end, returning False.
Complexity
Time Complexity: O(n), where n is the length of the path, as we iterate through the path once, with O(1) operations for each set lookup.
Space Complexity: O(n), as we store up to n coordinates in the set.
Approach 2: Simulate Movement on a 2D Plane
In this approach, we simulate movement on a 2D plane. Starting at the origin (0, 0), the path string is processed character by character to update the current position based on the direction: 'N' increases y, 'S' decreases y, 'E' increases x, and 'W' decreases x. A map or set records visits to each unique position. If a position is visited more than once, the path crosses itself.
In this Python function, a set keeps track of each position visited as (x, y) tuples. Starting at (0, 0), we iterate through the path, adjusting coordinates for each direction and checking against the set to detect crossings.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n), since every character in the path is processed.
Space Complexity: O(n), as we store coordinates in a set.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using a Set to Track Visited Coordinates | Time Complexity: O(n), where n is the length of the path, as we iterate through the path once, with O(1) operations for each set lookup. |
| Simulate Movement on a 2D Plane | Time Complexity: O(n), since every character in the path is processed. |
| Default Approach | — |
Detailed 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. |
Video Solution
Path Crossing - Leetcode 1496 - Python • NeetCodeIO • 14,757 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Path Crossing easy or hard?
Path Crossing Python/Java solution
How to solve Path Crossing in O(n)?
What is the best approach for Path Crossing?
Is Path Crossing asked at Google/Amazon/Meta?
What data structure is used in Path Crossing?
What is the time complexity of Path Crossing?
Ready to solve this problem?
Practice Path Crossing with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor