This is a nice application of DFS. I think this is a good question that exercises a few things. Briefly, the question is “given a grid, find the perimeter of the unique island”. To me the natural approach feels like, find the island, and then do a DFS exploration to touch its perimeter.

• From a pedagogical standpoint, I think it’s nice that it uses DFS, and “stretches” its application. In the [[1, 1], [1, 1]] example it made it clear that I couldn’t “double-count” any nodes!
• From an interview standpoint, it’s a nice mapping of intuitive(-enough) requirements to code.
• As always it’s a bit contrived, but I like questions where you have to synthesize higher-level data from smaller parts. I think that’s a good theme.

Solution, and detailed discussion, below

Solution

class Solution:
    def findLand(self, grid: List[List[int]]):
        for i, row in enumerate(grid):
            for j, cell in enumerate(row):
                if cell == 1:
                    return (i, j)
        return (-1, -1) # error state

    def islandPerimeter(self, grid: List[List[int]]) -> int:
        startLoc = self.findLand(grid)
        assert(startLoc[0] != -1)

        p = 0
        # DFS
        seen = set([])
        willProcess = set([startLoc])
        workList = [startLoc]
        while workList:
            i, j = workList.pop()
            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                # case 1: we know there cannot be a neighbor (edge of map) or water!
                if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[x]) or grid[x][y] == 0:
                    p += 1
                    continue
                # case 2: it's a neighbor we've seen:
                if (x, y) in seen:
                    continue
                # case 3: a new node to explore!
                if (x, y) not in willProcess:
                    willProcess.add((x, y))
                    workList.append((x, y))
            seen.add((i, j))
        return p

Discussion

• There’s some redundancy with “willProcess” and “seen”. I think I can get rid of “seen”?
• I make ready use of a lot of the conveniences of Python. Generating the list as the expression (in the for x, y in … loop), nevermind the ability to decompose those tuples, is really nice for these interviewing questions.
• Implicit in the code is sort of 2 layers: there’s the “straight” DFS, i.e., case 3, and then there’s also the “when I’m at a node, how does it contribute to the perimeter calculation”? Something in my mind, but not explicitly listed out, is that we process each node exactly once, and then we know that the node will contribute between 0 and 4 to the perimeter (depending on the 4 neighbors we check.
• I feel like it is crucial we don’t have lakes, as noted in the problem, but I can’t quite articulate why. Something to consider if/when I revisit this problem.

I like this! It touches on both matrix and graph problems (mainly graph problems) and hits a lot of “right notes”. More graph problems here.