Path Crossing

EASY

Description

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 <= 10⁴
path[i] is either 'N', 'S', 'E', or 'W'.

Approaches

Checkout 2 different approaches to solve Path Crossing. Click on different approaches to view the approach and algorithm in detail.

Brute Force with List

This approach simulates the path step by step and keeps track of all visited coordinates in a list. For each new coordinate, it iterates through the entire list of previously visited coordinates to check for a match.

Algorithm

Initialize current coordinates x = 0, y = 0.
Create a list of integer arrays, visitedPoints, to store the coordinates of each point visited.
Add the starting point {0, 0} to visitedPoints.
Iterate through each character move in the input path string.
Update x and y according to the direction specified by move.
After updating the coordinates, iterate through the visitedPoints list.
For each point in the list, check if its coordinates match the current (x, y).
If a match is found, it means the path has crossed itself, so return true.
If no match is found after checking all previous points, add the current {x, y} to visitedPoints.
If the loop completes without finding any crossing, return false.

The brute-force method involves a straightforward simulation of the walk. We maintain the current (x, y) coordinates, starting from the origin (0, 0). We use a dynamic list (like an ArrayList in Java) to store the history of all visited coordinates. The starting point (0, 0) is the first entry in our list. Then, for each move in the given path, we update our current coordinates. After each move, we perform a linear scan through our list of visited points to see if the new coordinate has been visited before. If it has, we've found a crossing and can immediately return true. Otherwise, we add the new coordinate to our list and proceed to the next move. If we process the entire path without finding any crossings, we return false.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isPathCrossing(String path) {
        List<int[]> visitedPoints = new ArrayList<>();
        int x = 0, y = 0;
        visitedPoints.add(new int[]{0, 0});

        for (char move : path.toCharArray()) {
            if (move == 'N') y++;
            else if (move == 'S') y--;
            else if (move == 'E') x++;
            else if (move == 'W') x--;

            for (int[] point : visitedPoints) {
                if (point[0] == x && point[1] == y) {
                    return true;
                }
            }
            visitedPoints.add(new int[]{x, y});
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the path. For each of the N steps, we may have to scan up to N previous points in the list. The total number of comparisons is roughly the sum of integers from 1 to N, which is O(N^2).Space Complexity: O(N), where N is the length of the path. In the worst-case scenario (when the path never crosses), we store all N+1 visited points in the list.

Pros and Cons

Pros:

Simple to understand and implement.
Doesn't require complex data structures beyond a basic list.

Cons:

Inefficient for long paths due to the nested loop structure, leading to a quadratic time complexity.
Can be slow and may result in a 'Time Limit Exceeded' error on platforms with strict time limits.

Code Solutions

Checking out 3 solutions in different languages for Path Crossing. Click on different languages to view the code.

class Solution {
public
  boolean isPathCrossing(String path) {
    int i = 0, j = 0;
    Set<Integer> vis = new HashSet<>();
    vis.add(0);
    for (int k = 0, n = path.length(); k < n; ++k) {
      switch (path.charAt(k)) { case 'N' -> -- i ; case 'S' -> ++ i ; case 'E' -> ++ j ; case 'W' -> -- j ; } int t = i * 20000 + j ; if (! vis . add ( t )) { return true ; } } return false ; } }

Video Solution

Watch the video walkthrough for Path Crossing

Data Structures:

Hash TableString

Companies:

Yandex |