Path Crossing

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'.
SOLUTION:
class Solution:
    def isPathCrossing(self, path: str) -> bool:
        x = 0
        y = 0
        visited = set()
        visited.add((x, y))
        for c in path:
            if c == 'N':
                y += 1
            if c == 'E':
                x += 1
            if c == 'S':
                y -= 1
            if c == 'W':
                x -= 1
            if (x, y) in visited:
                return True
            visited.add((x, y))
        return False

Comments

Post a Comment

Popular posts from this blog

Minimum Number of Operations to Move All Balls to Each Box

You have n boxes. You are given a binary string boxes of length n , where boxes[i] is '0' if the i th box is empty , and '1' if it contains one ball. In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1 . Note that after doing so, there may be more than one ball in some boxes. Return an array answer of size n , where answer[i] is the minimum number of operations needed to move all the balls to the i th box. Each answer[i] is calculated considering the initial state of the boxes.   Example 1: Input: boxes = "110" Output: [1,1,3] Explanation: The answer for each box is as follows: 1) First box: you will have to move one ball from the second box to the first box in one operation. 2) Second box: you will have to move one ball from the first box to the second box in one operation. 3) Third box: you will have to move one ball from the first box to the third box in two...
Read more

Efficient Generation of Nth Row of Binomial Coefficient Modulo M

Efficient Generation of Nth Row of Binomial Coefficient Modulo M Efficient Generation of Nth Row of Binomial Coefficient Modulo M Introduction Calculating the binomial coefficient (also known as the combinatorial coefficient) is a common task in mathematics and programming. However, when the modulo M is not prime, finding an efficient method becomes more challenging. In this article, we will explore a technique that allows us to efficiently generate the Nth row of the binomial coefficient modulo M, even when M is not necessarily prime. This technique utilizes prime factorization and a sieve algorithm to achieve efficient computation. The Implementation Let's take a look at the implementation of the technique: from collections import Counter N = 1 + 10 ** 6 v = [False] * N spf = [1] * N for i in range(2, N, 2): spf[i] = 2 for i in range(3, N, 2): if not v[i]: spf[i] = i j = i while j * i 1: ctr[spf[a]...
Read more

Lazy Deletion in Heap: A Wrapper for Python heapq

Lazy Deletion in Heap: A Wrapper for Python heapq Lazy Deletion in Heap: A Wrapper for Python heapq In many programming scenarios, we often encounter situations where we need to maintain a heap data structure and perform operations such as insertion, deletion, and retrieval of the minimum element efficiently. Python provides a built-in module called heapq that offers heap operations. However, the standard heapq module does not provide direct support for lazy deletion, which can be useful in certain cases. In this article, we will explore a wrapper class, Heap , that extends the functionality of the Python heapq library to support lazy deletion in a heap. The Heap Class The Heap class is a wrapper that encapsulates the heapq module to enable lazy deletion in a heap. Let's go through its main methods and their functionalities: __init__(self) : Initializes the Heap instance by creating an empty heap and a defaultdict to track the deleted elements ...
Read more