1496. Path Crossing

EasyHash TableString
Leetcode Link

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.

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.

  1. Initialize the current position to the origin, (i, j) = (0, 0).
  2. 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.
  3. Loop through each character in the path string:
    • The for c in path: loop iterates over each character in the path string.
    • The match statement (a feature available in Python 3.10 and above) works like a switch-case statement found in other languages. It matches the character c with one of the cases: 'N', 'S', 'E', or 'W'.
    • Based on the direction, we update our (i, j) coordinates:
      • For 'N', we decrement i to move north (i -= 1).
      • For 'S', we increment i to move south (i += 1).
      • For 'E', we increment j to move east (j += 1).
      • For 'W', we decrement j to move west (j -= 1).
  4. After updating the coordinates, we check if the new position (i, j) is already present in the vis set:
    • If the condition (i, j) in vis: is True, we return True since 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)).
  5. If the loop completes without finding any crossing, the return False statement at the end of the function ensures we return False, 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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

  1. We initialize our current position at the origin (0, 0), so (i, j) = (0, 0).
  2. We create an empty set vis and add the initial position to it, so vis = {(0, 0)}.
  3. We start looping through each character in the path:
    • The first character is 'N'. We decrement i because we're moving north, so i = 0 - 1 = -1 and j remains 0. The new position is (-1, 0), which is not in vis, so we add it: vis = {(0, 0), (-1, 0)}.
    • The second character is 'E'. We increment j to move east, so i remains -1, and j = 0 + 1 = 1. The new position is (-1, 1), which is also not in vis, so we add it: vis = {(0, 0), (-1, 0), (-1, 1)}.
    • The third character is 'S'. We increment i to move south, so i = -1 + 1 = 0 and j remains 1. The new position is (0, 1), not in vis, so we add it: vis = {(0, 0), (-1, 0), (-1, 1), (0, 1)}.
    • The fourth character is 'W'. We decrement j to move west, so i remains 0, and j = 1 - 1 = 0. The position (0, 0) is already in vis, indicating we've returned to the origin. Since this position is revisited, we would return True as the path crosses itself.

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
30
1class 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}
45
1#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};
44
1function 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}
40

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following uses divide and conquer strategy?


Recommended Readings