Tag Archives: dfs

Island Perimeter (Leetcode)

January 8, 2023 Aaron

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.

Interview Questions

Path Finder 1 (Code Wars 16)

December 11, 2021 Aaron Leave a comment

Variation on island finding. Which is to say, more depth-first-search. Embarrassingly, I forgot some the base case!

def neighbors(maze, i, j):
    toTry = []
    if i > 0:
        toTry.append((i-1, j))
    if j > 0:
        toTry.append((i, j-1))
    if i + 1 < len(maze):
        toTry.append((i+1, j))
    if j + 1 < len(maze[i]):
        toTry.append((i, j+1))
    final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
    return final
def path_finder(maze):
    maze = maze.split()
    for row in maze:
        assert(len(row) == len(maze))
    seen = set([])
    toVisit = [(0,0)]
    seen.add((0, 0))
    target = (len(maze)-1, len(maze)-1)
    while toVisit:
        i, j = toVisit.pop()
        for (a, b) in neighbors(maze, i, j):
            if (a, b) in seen:
                continue
            seen.add((a, b))
            toVisit.append((a, b))
    return target in seen

Interview Questions

Count Islands (Leetcode 16)

December 6, 2021 Aaron Leave a comment

Did this one a while ago. “Just” an exercise in DFS, counting connected subgraph or something. A nice enough word-problem for exercising “recognizing” when graphs appear. Ah, that’s a nice topic to consider.

class Solution(object):
    def visited(self, i, j):
        return (i, j) in self.seenSet
    def mark(self, i, j):
        self.seenSet.add((i, j))
    def neighbors(self, i, j):
        ns = []
        if i > 0:
            ns.append((i-1, j))
        if j > 0:
            ns.append((i, j-1))
        if i < (len(self.grid) - 1):
            ns.append((i+1, j))
        if j < (len(self.grid[0]) - 1):
            ns.append((i, j+1))
        return ns
    def markIsland(self, i, j):
        assert(self.grid[i][j] == '1')
        assert(not self.visited(i, j))
        toMark = [(i, j)]
        while toMark:
            i, j = toMark.pop()
            if self.visited(i, j):
                continue
            self.mark(i, j)
            for n in self.neighbors(i, j):
                a, b = n
                if self.grid[a][b] == '1':
                    if not self.visited(a, b):
                        toMark.append(n)
                        
    def numIslands(self, grid):
        self.seenSet = set([])
        self.grid = grid
        islandCount = 0
        for i in range(len(grid)): # for each row
            for j in range(len(grid[i])): # for each column
                if grid[i][j] == "0":
                    continue
                if self.visited(i, j):
                    continue
                self.markIsland(i, j)
                islandCount+=1
        return islandCount

Aaron and Algorithms