note: this is not meant to throw shade on LeetCode or other such platforms. They do offer premium, focused sessions to help people who have my use case. Perhaps this may showcase for some why such an approach might be worth paying for.

I was using LeetCode earlier last year to learn rust. Often I would run into an issue of a crate not being available, or something, and ultimately the community I am a part of in discord would only begrudingly help me through it, complaining that this is no way to learn rust. I gave up that approahc because there were so many tooling issues, but I used to love sites like leetcode from long ago and assumed they were still pretty good.

Today I am preparing for interviews and ran into a bfs/dfs question in the task list I was working through, which was on leet code: surrounded regions.

You get a solution template like:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.

        dfs on border o
        all non-enoucntered coordinates should be x
        """
        pass

From the problem description, I realized that I can search from the border inward to find all adjoint sets of coordinates that should not be flipped. Everything else should be flipped to 'X'.

I set about solving it piece-meal; first I wrote the code that should work:

from collections import namedtuple

Coord = namedtuple('Coord', ['y', 'x'])
...
    def solve(self, board: List[List[str]]) -> None:

        self.board = board
        self.visited = set() # I'll keep track of what I already worked on

        # get all members of the disjoint sets of bordered adjacencies
        unflippable = set()
        visit_stack = self.get_border()
        for coord in visit_stack:
            if board[coord.y][coord.x] == 'O':
                adjacencies = self.bfs(coord)
                unflippable.update(adjacencies)

        # update the board
        for y in range(len(board)):
            for x in range(len(board[y])):
                if Coord(y,x) in unflippable:
                    board[y][x] = 'O'
                else:
                    board[y][x] = 'X'

and then I fleshed out the rest of the solution:

from queue import Queue
from typing import List, Set
...
    def get_border(self) -> Set[Coord]:
        height = len(self.board) - 1
        width = len(self.board[0]) - 1
        border_elements = set()

        border_elements.update([Coord(y=0, x=x) for x in range(width + 1)])
        border_elements.update([Coord(y=len(self.board) - 1, x=x) for x in range(width + 1)])
        for y in range(1, height):
            border_elements.add(Coord(y, x=0))
            border_elements.add(Coord(y, x=width))

        return border_elements

    def bfs(self, coord: Coord) -> Set[str]:
        adjacencies = set()
        q = Queue()
        q.put(coord)
        while not q.empty():
            pos = q.get()
            self.visited.add(pos)
            if self.board[pos.y][pos.x] == 'O':
                adjacencies.add(pos)
                surrounds = self.get_surrounding_coords(pos)
                for candidate in surrounds:
                    if candidate not in self.visited:
                        q.put(candidate)

        return adjacencies

    def get_surrounding_coords(self, coord: Coord) -> Set[Coord]:
        surrounds = set()

        offsets = [Coord(-1,0), Coord(1,0), Coord(0,-1), Coord(0,1)]
        for offset in offsets:
            candidate = Coord(y=coord.y + offset.y, x=coord.x + offset.x)
            if self.is_valid_coord(candidate):
                surrounds.add(candidate)

        return surrounds

    def is_valid_coord(self, coord: Coord) -> bool:
        return coord.y > 0 \
                and coord.x > 0 \
                and coord.y < len(self.board) \
                and coord.x < len(self.board[coord.y])

Something that I failed to see, because I did not go back and refactor, was that self.visited and unflippable are the same, but this does not meaningfully change the runtime, just the space complexity. However, the answer is not accepted, as "exceeding the time limit".

Analyzing it, I realized that it could be further optimized, but not terribly much so. So, when you hit a bit of a wall, you should not keep working it until you solve, but rather use it as a learning opportunity. I looked for someone else's bfs solution, and rewrote it for clarity:

    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.

        dfs on border o
        all non-enoucntered coordinates should be x
        """

        if len(board) <=2 or len(board[0]) <=2:
            return

        q = deque()
        rows = len(board)
        cols = len(board[0])
        q.extend([(y, x) for y in range(rows) for x in [0, cols - 1] if board[y][x] == 'O'])
        q.extend([(y, x) for x in range(cols) for y in [0, rows - 1] if board[y][x] == 'O'])

        visited = set()
        offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        is_valid = lambda y, x: y >= 0 and x >= 0 and y < rows and x < cols
        while q:
            origin_y, origin_x = q.popleft()
            for (oy, ox) in offsets:
               y = origin_y + oy
               x = origin_x + ox
               if is_valid(y,x) and (y,x) not in visited and board[y][x] == 'O':
                   q.append((y,x))
                   visited.add((y,x))

        for y in range(1, rows - 1):
            for x in range(1, cols - 1):
                if board[y][x] == 'O' and (y,x) not in visited:
                    board[y][x] = 'X'

It's very much shorter, but is it any better? I felt like this was essentially the same approach. So I asked dolphin-mixtral 8x7b (a local GPT-like LLM I am running, specialized for code). If it is correct, and for my part I don't see a reason to dismiss it. (edited for brevity):

The difference between these two solutions is not in their time complexity, but rather in their approach to solving the problem. Both of these solutions should have a similar time complexity, which is O(m * n) where m and n are the dimensions of the board. This is because both of these solutions perform a breadth-first search (BFS) on the grid to find all the cells that are connected to the border cells.

The main differences between these two solutions are in their implementation details. The first solution uses list comprehensions to add all the border cells to the queue, while the second solution uses a separate method called get_border() to achieve the same goal. Additionally, the first solution uses a set to keep track of visited cells, while the second solution uses a set to keep track of unflippable cells.

In terms of readability and maintainability, the second solution is more modular and easier to understand, since it separates the different components of the algorithm into separate methods. However, this comes at the cost of being slightly longer than the first solution.

In an interview, excessive "boilerplate" should be avoided in solutions. However, interviewers typically wouldn't criticize such an approach unless there is not the time for it. If time is limited, the interviewer's input should aid in code reduction; they would help me to reduce my code, and I feel confident that together we would get there. Overall, I prioritize maintainable and readable code. LeetCode often fails to discern when function calls don't significantly impact overall complexity, mistakenly flagging modular and easily understandable code as exceeding runtime complexity limits.