Problem statement

https://binarysearch.com/problems/Roomba-Sequel/

Solution 1

We can use Leetcode 0352. Data Stream as Disjoint Intervals problem here. For each new cell (x, y) we have, when we add we need to update horizontal and vertical intervals. Also we can have a case such as [1, 5], [7, 12] and when we add 6, we want to know the ends for this point. Then we start to traverse our path and depending on direction we update our ranges

Complexity

It is O(n) for time and space.

Code

class SummaryRanges:
    def __init__(self):
        self.d1, self.d2, self.al = {}, {}, set()

    def add(self, v):
        if v in self.al: return
        self.al.add(v)
        i1 = self.d2.get(v - 1, -1)
        i2 = self.d1.get(v + 1, -1)
        lft, rgh = v - 1 in self.d2, v + 1 in self.d1
                
        if lft and rgh:
            self.d1[i1] = self.d1[v] = i2
            self.d2[i2] = self.d2[v] =  i1
        elif lft and not rgh:
            self.d1[i1] = v
            self.d2[v] = i1
        elif not lft and rgh:
            self.d2[i2] = v
            self.d1[v] = i2
        else:
            self.d1[v] = v
            self.d2[v] = v
            
        self.d2.pop(v - 1, None)
        self.d1.pop(v + 1, None)

class Solution:
    def solve(self, moves, x0, y0):
        rows = defaultdict(SummaryRanges)
        cols = defaultdict(SummaryRanges)
        rows[0].add(0)
        cols[0].add(0)
        print(rows[0])
        x, y = 0, 0
        for move in moves:
            if move == "EAST":
                if x + 1 not in rows[y].al:
                    x2, y2 = x + 1, y
                else:
                    x2, y2 = rows[y].d1[x] + 1, y
            elif move == "WEST":
                if x - 1 not in rows[y].al:
                    x2, y2 = x - 1, y
                else:
                    x2, y2 = rows[y].d2[x] - 1, y
            elif move == "NORTH":
                if y + 1 not in cols[x].al:
                    x2, y2 = x, y + 1
                else:
                    x2, y2 = x, cols[x].d1[y] + 1
            else:
                if y - 1 not in cols[x].al:
                    x2, y2 = x, y - 1
                else:
                    x2, y2 = x, cols[x].d2[y] - 1
            rows[y2].add(x2)
            cols[x2].add(y2)
            x, y = x2, y2

        return (x0, y0) == (x, y)

Solution 2

Actually, it can be written in sorter way, I borrowed code from lucifer1004 here. We create neibs is list of dictionaries, where for example neibs[0] are the closest empty cell in NORTH direction. When we add new cell, we need to update neibs in all 4 directinos.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, moves, tx, ty):
        dr = {"N": 0, "W": 1, "E": 2, "S": 3}
        dx = [0, -1, 1, 0]
        dy = [1, 0, 0, -1]
        neibs = [{} for _ in range(4)]

        def get(x, y, d):
            if (x, y) in neibs[d]:
                return neibs[d][(x, y)]
            return (x + dx[d], y + dy[d])

        def connect(x, y):
            for d in range(2):
                p = get(x, y, d)
                q = get(x, y, 3 - d)
                neibs[3 - d][p] = q
                neibs[d][q] = p

        x, y = 0, 0
        for move in moves:
            connect(x, y)
            x, y = get(x, y, dr[move[0]])

        return x == tx and y == ty