Path Crossing

Easy

#1380Time: 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: 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.1 company

Data structures

Hash Table String

Companies

Yandex

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean isPathCrossing(String path) {6        List<int[]> visitedPoints = new ArrayList<>();7        int x = 0, y = 0;8        visitedPoints.add(new int[]{0, 0});9 10        for (char move : path.toCharArray()) {11            if (move == 'N') y++;12            else if (move == 'S') y--;13            else if (move == 'E') x++;14            else if (move == 'W') x--;15 16            for (int[] point : visitedPoints) {17                if (point[0] == x && point[1] == y) {18                    return true;19                }20            }21            visitedPoints.add(new int[]{x, y});22        }23        return false;24    }25}

Complexity

Time

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

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.

Trade-offs

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.

This approach improves upon the brute-force method by using a HashSet to store visited coordinates. A HashSet provides average O(1) time complexity for lookups, which significantly speeds up the process of checking if a coordinate has been visited before.

Algorithm

Initialize current coordinates x = 0, y = 0.
Create a HashSet of strings, visited, to store unique visited coordinates.
To store a coordinate pair (x, y) in the set, convert it to a unique string format, e.g., "x,y".
Add the string representation of the starting point, "0,0", to the visited set.
Iterate through each character move in the path string.
Update x and y based on the move.
Create the string key for the new coordinate.
Attempt to add the key to the visited set. The add method returns false if the key is already present.
If add returns false, a crossing has occurred, so return true.
If the loop finishes, it means no point was revisited, so return false.

Walkthrough

To optimize the check for previously visited points, we can replace the list with a HashSet. A HashSet allows for checking the existence of an element in average constant time, O(1). The overall algorithm remains similar: we traverse the path and update our coordinates. However, instead of a linear scan, we use the HashSet to check for previous visits. To store a 2D coordinate pair (x, y) in the set, we need a hashable representation. A simple and effective way is to convert the pair into a unique string, such as "x,y". We start by adding the origin "0,0" to the set. For each move, we update (x, y), create the corresponding string key, and try to add it to the set. If the add operation fails (because the key is already in the set), we have found a crossing and return true. Otherwise, the new key is added, and we continue. If we traverse the entire path, we return false.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public boolean isPathCrossing(String path) {6        Set<String> visited = new HashSet<>();7        int x = 0, y = 0;8        visited.add("0,0");9 10        for (char move : path.toCharArray()) {11            if (move == 'N') y++;12            else if (move == 'S') y--;13            else if (move == 'E') x++;14            else if (move == 'W') x--;15 16            String currentPos = x + "," + y;17            if (!visited.add(currentPos)) {18                // add() returns false if the element is already in the set19                return true;20            }21        }22        return false;23    }24}

Complexity

Time

O(N), where N is the length of the path. We iterate through the path once. Each operation inside the loop (coordinate update, string creation, and HashSet insertion/lookup) takes, on average, constant time, O(1).

Space

O(N), where N is the length of the path. In the worst case, if the path never crosses, the `HashSet` will store N+1 unique coordinate strings.

Trade-offs

Pros

Highly efficient with a linear time complexity of O(N).
This is the optimal solution for the given constraints.

Cons

Requires extra space for the HashSet.
Incurs a small overhead from string creation and hashing, though this is generally negligible.

Solutions

Solution

1class Solution {2public3  boolean isPathCrossing(String path) {4    int i = 0, j = 0;5    Set<Integer> vis = new HashSet<>();6    vis.add(0);7    for (int k = 0, n = path.length(); k < n; ++k) {8      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 ; } }

1class Solution {2public:3  bool isPathCrossing(string path) {4    int i = 0, j = 0;5    unordered_set<int> s{{0}};6    for (char &c : path) {7      if (c == 'N') {8        --i;9      } else if (c == 'S') {10        ++i;11      } else if (c == 'E') {12        ++j;13      } else {14        --j;15      }16      int t = i * 20000 + j;17      if (s.count(t)) {18        return true;19      }20      s.insert(t);21    }22    return false;23  }24};

1class Solution:2    def isPathCrossing(self, path: str) -> bool: i = j = 0 vis = {(0, 0)} for c in path: match c: case 'N': i -= 1 case 'S': i += 1 case 'E': j += 1 case 'W': j -= 1 if (i, j) in vis: return True vis . add((i, j)) return False

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem