Problem statement

https://binarysearch.com/problems/Continuous-Path-to-Escape-Mines/

Solution

The idea is to create graph with nodes our mines and left and right borders. Then we need to check if we can reach from node 0 node n + 1, which can be done with union find.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def solve(self, A, width):
        n = len(A)
        dsu = DSU(n + 2)
        for i in range(n):
            for j in range(i + 1, n):
                x1, y1, r1 = A[i]
                x2, y2, r2 = A[j]
                if (x1 - x2)**2 + (y1 - y2)**2 <= (r1 + r2)**2:
                    dsu.union(i + 1, j + 1)
        
        for i in range(n):
            x, y, r = A[i]
            if x <= r: dsu.union(0, i + 1)
            if x >= width - r: dsu.union(i + 1, n + 1)

        return dsu.find(0) != dsu.find(n + 1)