1496. Path Crossing
Problem Description
In this LeetCode problem, we are given a string path that represents a sequence of moves. Each character in path stands for a directional move: 'N' for north, 'S' for south, 'E' for east, and 'W' for west. Each move is one unit long. We start at the origin point (0, 0) on a two-dimensional plane and follow the moves indicated in the path string. The task is to determine whether or not our path ever crosses itself. In other words, if we ever visit the same point more than once during our walk, we return true. If our path does not cross and we never visit the same point more than once, we return false.
Intuition
To solve this problem, the intuitive approach is to track every position we visit as we traverse the path defined by the string. We can use a set to store our visited positions because sets allow fast lookup times to check whether we have been to a position or not, as duplicates are not allowed in a set.
We start by initializing our position to the origin (0, 0) and create an empty set called vis (short for "visited") which will hold tuples of our coordinates on the 2D plane. As we iterate over each move in the path string, we update our current position by incrementing or decrementing our i (for the north-south axis) and j (for the east-west axis) accordingly.
After each move, we check whether the new coordinate (represented as a tuple (i, j)) is already present in our vis set. If it is, it means we've just moved to a spot we've previously visited, which means our path has crossed, and we return true. If the coordinate is not in the set, we add it to the set and continue onto the next move in the path.
We repeat this process for each move in the path. If we finish iterating over all moves without returning true, it means our path never crosses itself, and we return false.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Solution Approach
The solution to the problem implemented in Python uses a set data structure and simple coordinate manipulation to track the movement on the path. Below is an overview of the approach, breaking down how the algorithm works.
- Initialize the current position to the origin,
(i, j) = (0, 0). - Create a set named
vis(short for visited) and add the initial position to it. Sets are chosen because they store unique elements, allowing us to quickly check if a position has been visited before. - Loop through each character in the
pathstring:- The
for c in path:loop iterates over each character in thepathstring. - The
matchstatement (a feature available in Python 3.10 and above) works like a switch-case statement found in other languages. It matches the charactercwith one of the cases: 'N', 'S', 'E', or 'W'. - Based on the direction, we update our
(i, j)coordinates:- For 'N', we decrement
ito move north (i -= 1). - For 'S', we increment
ito move south (i += 1). - For 'E', we increment
jto move east (j += 1). - For 'W', we decrement
jto move west (j -= 1).
- For 'N', we decrement
- The
- After updating the coordinates, we check if the new position
(i, j)is already present in thevisset:- If the condition
(i, j) in vis:isTrue, we returnTruesince the path has crossed a previously visited position. - If the position is not found in the set, we add the new position to the set with
vis.add((i, j)).
- If the condition
- If the loop completes without finding any crossing, the
return Falsestatement at the end of the function ensures we returnFalse, as no path has been crossed.
This approach uses straightforward coordinate tracking and set membership checks to efficiently solve the problem. The time complexity is O(N), where N is the length of the path, since we visit each character once, and the space complexity is also O(N), due to the storage required for the set that holds the visited positions.
What's the relationship between a tree and a graph?
Example Walkthrough
Let's assume our given path string is "NESWW".
Following the solution approach, here's a step-by-step illustration of how the algorithm will execute:
- We initialize our current position at the origin (0, 0), so
(i, j) = (0, 0). - We create an empty set
visand add the initial position to it, sovis = {(0, 0)}. - We start looping through each character in the
path:- The first character is 'N'. We decrement
ibecause we're moving north, soi = 0 - 1 = -1andjremains 0. The new position is(-1, 0), which is not invis, so we add it:vis = {(0, 0), (-1, 0)}. - The second character is 'E'. We increment
jto move east, soiremains -1, andj = 0 + 1 = 1. The new position is(-1, 1), which is also not invis, so we add it:vis = {(0, 0), (-1, 0), (-1, 1)}. - The third character is 'S'. We increment
ito move south, soi = -1 + 1 = 0andjremains 1. The new position is(0, 1), not invis, so we add it:vis = {(0, 0), (-1, 0), (-1, 1), (0, 1)}. - The fourth character is 'W'. We decrement
jto move west, soiremains 0, andj = 1 - 1 = 0. The position(0, 0)is already invis, indicating we've returned to the origin. Since this position is revisited, we would returnTrueas the path crosses itself.
- The first character is 'N'. We decrement
Therefore, the function would return True based on the input path "NESWW", because we revisited the starting point, indicating a crossing path.
Solution Implementation
1class Solution:
2 def isPathCrossing(self, path: str) -> bool:
3 # initialize starting point
4 x, y = 0, 0
5 # set to keep track of visited coordinates
6 visited = {(0, 0)}
7
8 # iterate over each character in the path string
9 for direction in path:
10 # move in the corresponding direction
11 if direction == 'N':
12 x -= 1
13 elif direction == 'S':
14 x += 1
15 elif direction == 'E':
16 y += 1
17 elif direction == 'W':
18 y -= 1
19
20 # check if the new position has already been visited
21 if (x, y) in visited:
22 # if we've been here before, path crosses. Return True
23 return True
24
25 # add the new position to the set of visited coordinates
26 visited.add((x, y))
27
28 # if visited all positions without crossing, return False
29 return False
301class Solution {
2
3 public boolean isPathCrossing(String path) {
4 // Two variables to keep track of current position
5 int x = 0, y = 0;
6 // Use a HashSet to store visited coordinates.
7 Set<Integer> visited = new HashSet<>();
8 // Hash for the origin, adding it as the first visited coordinate
9 visited.add(0);
10
11 // Iterate over the path characters
12 for (int index = 0; index < path.length(); ++index) {
13 char direction = path.charAt(index);
14
15 // Move in the grid according to the current direction
16 switch (direction) {
17 case 'N': // Moving north decreases the y-coordinate
18 y--;
19 break;
20 case 'S': // Moving south increases the y-coordinate
21 y++;
22 break;
23 case 'E': // Moving east increases the x-coordinate
24 x++;
25 break;
26 case 'W': // Moving west decreases the x-coordinate
27 x--;
28 break;
29 }
30
31 // Calculate a unique hash for the current position.
32 // Multiplying by a large enough number to not mix coordinates
33 int hash = y * 20000 + x;
34
35 // Check if this position has been visited before, if so, path crosses
36 if (!visited.add(hash)) {
37 return true; // early return if the path crosses itself
38 }
39 }
40
41 // If no crossing points were found, return false
42 return false;
43 }
44}
451#include <unordered_set>
2#include <string>
3
4class Solution {
5public:
6 // Determines if a path crosses itself based on commands in a string
7 bool isPathCrossing(const std::string& path) {
8 // Initialize (i, j) as the starting position (0, 0)
9 int x = 0, y = 0;
10
11 // Create a hash set to track visited positions with a unique key
12 std::unordered_set<int> visitedPositions{{0}};
13
14 // Iterate through each character in the path string
15 for (const char &direction : path) {
16 // Update position based on direction
17 if (direction == 'N') {
18 --x; // Move north
19 } else if (direction == 'S') {
20 ++x; // Move south
21 } else if (direction == 'E') {
22 ++y; // Move east
23 } else {
24 --y; // Move west
25 }
26
27 // Calculate a unique key for the position
28 int key = x * 20001 + y; // Use prime number to reduce collisions
29
30 // Check if the position has been visited before
31 if (visitedPositions.count(key)) {
32 // If visited before, path crosses itself
33 return true;
34 }
35
36 // Add the new position to the set of visited positions
37 visitedPositions.insert(key);
38 }
39
40 // If no crossing occurred, return false
41 return false;
42 }
43};
441function isPathCrossing(path: string): boolean {
2 // Initialize current position at the origin (0,0)
3 let position: [number, number] = [0, 0];
4 // Create a set to store visited coordinates as a unique identifier
5 const visited: Set<string> = new Set();
6
7 // Add the starting position (origin) to the visited set
8 visited.add(position.toString());
9
10 // Iterate through each character in the path string
11 for (const direction of path) {
12 // Update the position according to the direction
13 switch (direction) {
14 case 'N': // North decreases the x coordinate
15 position[0]--;
16 break;
17 case 'S': // South increases the x coordinate
18 position[0]++;
19 break;
20 case 'E': // East increases the y coordinate
21 position[1]++;
22 break;
23 case 'W': // West decreases the y coordinate
24 position[1]--;
25 break;
26 }
27
28 // Convert the tuple to a string to create a unique identifier for the position
29 const positionKey = position.toString();
30 // If the position has been visited, return true and exit
31 if (visited.has(positionKey)) {
32 return true;
33 }
34 // Add the new position to the visited set
35 visited.add(positionKey);
36 }
37 // If no crossing paths are detected, return false
38 return false;
39}
40Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Time and Space Complexity
The given Python code checks if a path crosses itself based on a string of movement commands ('N', 'S', 'E', 'W' corresponding to North, South, East, and West movements). The code uses a set vis to track all the visited coordinates.
Time Complexity:
The time complexity of the code is O(n), where n is the length of the input string path. This is because the code iterates through each character of the path string exactly once.
For each character, the operations performed (updating coordinates and checking the set for the existence of the coordinates) are constant time operations, thus each character in the path requires a constant amount of time processing.
Space Complexity:
The space complexity of the code is O(n), where n is the length of the input string path. In the worst case, none of the positions will be revisited, so the set vis will contain a unique pair of coordinates for each move in the path. Thus, the maximum size of the set is proportional to the number of movements, which corresponds to the length of the path.
In summary, the code has a linear time and space complexity with respect to the length of the input path.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.