Solving common graph problems (2d grid) on leetcode

1_leetcode-graph-notes.txt

Grid problems are almost always just graph problems and typically straightforward ones. I initially found them a bit weird because in algorithm classes they present graphs as adjacency nodes or adjacency matrices. In a grid, each cell is a node, and it's neighbors are the four-directional neighboring cells or sometimes 8-directional, if the problem at hand allows travel in all the diagonals in addition to up, down, left, right. The vertices are not explicit but usually we don't need to worry about them in these problems. 

There is nothing special about a grid vs another type of graph representation. Just need to tweak the grpah algorithms at our disposal.

Basic graph techniques:

BFS- traverses the entire graph, going layer by layer expanding from the starting point. It allows us to do a couple of things, count connected components in a graph, find the shortest distance from one cell to another cell. While traversing,
we need to track visited cells. You can do that by changing the cell value (coloring) or recording the coordinate in a data structure, (2d array, set, hashtable). We can dictate the behavior by specifying what requirements a cell needs to meet in order to be added to the queue of cells to be explored. So in a grid with only 0s and 1s, we can use bfs to traverse only the cells with value of 1.

DFS- traverses the entire graph, except it exhausts one direction first before trying a different direction. Also accomplishes the same things as BFS except it cannot find the shortest path in an undirected graph. But sometimes our problem requires traversal in a single direction first. A lot of binary tree problems require this "depth first" behavior.

For the most part, bfs and dfs are interchangeable for many 2d grid problems.


Topological Sorting (in-degree, out-degree)


LC 200. Number of Islands 

This problem asks us to find the number of groups of 1's in a 2d grid. I start by thinking about how to separate the groups.
Thinking back to the graph strategies we have at our disposal, one is to use a traversal starting at each 1. The traversal
will find all of the connected 1's. Each time a traversal runs, a new island is found. Simply count number of times traversal runs. Traversal can be bfs or dfs. 

1 1 0 -> explore(0, 0)     x x 0  -> explore(0, 1) // nothing happens, (0, 1) was visited by explore(0, 0) 
1 0 0                      x 0 0
1 0 1                      x 0 1 

.... -> explore(2, 2)      x x 0
                           x 0 0
                           x 0 x 
                           
In total explore was called twice so our counter is 2. That is the number of islands in the input.
                           
In this example, we setup use two nested for loops to traverse the grid. At each cell, if the cell value is 1, run traverse and increment a counter each time traverse finishes an exploration. But this would return 5 (islands).
What we need to also do is keep track of visited cells with value 1, such that each cell is visited only once. There are
basically two ways to accomplish this, use a visited set, or modify the cell value. Both are fine, one uses more space, the other destroys the original input but saves space.


References: 
https://en.wikipedia.org/wiki/Degree_(graph_theory) 
https://en.wikipedia.org/wiki/Topological_sorting 
https://cs.stackexchange.com/questions/4914/why-cant-dfs-be-used-to-find-shortest-paths-in-unweighted-graphs 
https://en.wikipedia.org/wiki/Directed_acyclic_graph 

         

200_number_of_islands.py

from collections import deque


def countIslands(grid):
    island_count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                bfs(grid, i, j)
                island_count += 1
    print(grid)
    return island_count


def bfs(grid, r, c):
    queue = deque([(r, c)])
    m, n = len(grid), len(grid[0])
    while queue:
        row, col = queue.popleft() # pop off from left, mark as visited (change value to '2') and explore the neighbors.
        grid[row][col] = '2'
        for d in [(0, 1), (1, 0), (0, -1), (-1, 0)]:  # each cell connected to 4 neighbors, this is given by the problem statement.
            new_row, new_col = d[0]+row, d[1]+col
            if 0 <= new_row < m and 0 <= new_col < n:
                if grid[new_row][new_col] == '1':
                    queue.append((new_row, new_col)) #push the neighbors with value == '1' to back of queue. 
    print('done')


print(countIslands([['1', '1', '0'],
                    ['1', '0', '0'],
                    ['1', '0', '1']]))

# almost identical to countIslands2, except using visited set to track visited nodes instead of modifying grid
def countIslands2(grid):
    island_count = 0
    visited = set()
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1' and (i, j) not in visited:
                bfs2(grid, i, j, visited)
                island_count += 1
    print(grid)
    return island_count


def bfs2(grid, r, c, visited):
    queue = deque([(r, c)])
    m, n = len(grid), len(grid[0])
    while queue:
        row, col = queue.popleft()
        visited.add((r, c))
        for d in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            new_row, new_col = d[0]+row, d[1]+col
            if 0 <= new_row < m and 0 <= new_col < n:
                if grid[new_row][new_col] == '1' and (new_row, new_col) not in visited:
                    queue.append((new_row, new_col))
                    visited.add((new_row, new_col))
                    
 
# explore and color the grid using recursive dfs
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0 
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1 
        return count 
    
    def dfs(self, grid, r, c):
        grid[r][c] = '2'
        for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nr, nc = d[0]+r, d[1]+c 
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == '1':
                self.dfs(grid, nr, nc)
        

419_battleships_in_a_board.py

# leetcode 419
from collections import deque


class Solution:
    def countBattleships(self, board):
        count = 0
        visited = set()
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X' and (i, j) not in visited:
                    self.bfs(board, i, j, visited)
                    count += 1
        return count

    def bfs(self, board, r, c, visited):
        queue = deque([(r, c)])
        while queue:
            curR, curC = queue.popleft()
            visited.add((curR, curC))
            for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nr, nc = d[0]+curR, d[1]+curC
                if 0 <= nr < len(board) and 0 <= nc < len(board[0]) and (nr, nc) not in visited and board[nr][nc] == 'X':
                    queue.append((nr, nc))
                    visited.add((nr, nc))