Problem 1496 (Dec 23)

(Last updated: )

Question statement:

Given a string $\texttt{path}$, where $\texttt{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 $\texttt{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 $\texttt{false}$ otherwise.

Solution

Main idea:

  • Start a new (hash) set $\texttt{pos = [(0,0)]}$
  • Go through $\texttt{path}$ and for each new direction, calculuate current position in the 2D grid.
  • Check if current position is already in $\texttt{pos}$. If so, return $\texttt{True}$.
  • If not, append $\texttt{pos}$ with the current position.
  • Return $\texttt{False}$ if end of $\texttt{path}$ is reached.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def isPathCrossing(self, path: str) -> bool:
    posx = 0
    posy = 0
    p = set()
    p.add((posx, posy))
    for i in range(len(path)):
        if(path[i] == 'N'):
            posy += 1
        if(path[i] == 'S'):
            posy -=1
        if(path[i] == 'E'):
            posx +=1
        if(path[i] == 'W'):
            posx -=1
        pos = (posx, posy)
        if(pos in p):
            return True
        p.add(pos)
    return False

Comments:

Time complexity: O(n).

At the time of submission, the above solution passes leetcode submission cases in 35ms, beats 83.59% of users. It uses 17.2MB of memory, beating 72.13% of users.