Problem statement

https://binarysearch.com/problems/Blocked-Pipeline/

Solution

Not the fastest solution, but I tried to make it univerasal. Notice, that there can be several types of blockages:

.X X. X X. .X X

So, we can create counter for each blockage: how many nodes from this blockage we have so far. If we have two, then we can say that it is fully blocked. Then when we add or remove element, we check for each possible blockage if it is fully blocked or not. We are happy if we do not have fully blocked blockages.

Complexity

It is O(n + q) for time and O(n) for space, where q = len(R).

Code

class Solution:
    def solve(self, n, R):
        G = [[0, 0] for _ in range(n)]
        pairs = [(2*n-2, 2*n-1)]
        d = defaultdict(list)
        covered = Counter()
        for i in range(n - 1):
            pairs += [(2*i, 2*i + 1)]
            pairs += [(2*i, 2*i + 3)]
            pairs += [(2*i + 1, 2*i + 2)]

        for x, y in pairs:
            d[x] += [y]
            d[y] += [x]

        ans, total, V = 0, 0, [0]*(2*n)

        for r, c, t in R:
            x = r + 2*c
            if t == 1 and V[x] == 0:
                for y in d[x]:
                    a, b = min(x, y), max(x, y)
                    covered[a, b] += 1
                    if covered[a, b] == 2: total += 1
                V[x] = 1
            elif t == 0 and V[x] == 1:
                for y in d[x]:
                    a, b = min(x, y), max(x, y)
                    covered[a, b] -= 1
                    if covered[a, b] == 1: total -= 1
                V[x] = 0

            ans += (total == 0)      
        return ans