Scale Engineer

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 TableString
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 <= 104
  • 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.

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

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.

Solutions

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 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 →

Next problem