DFS & BFS

March 05, 2021

Leetcode problems about Depth-First Search & Breadth-First Search.

200. Number of Islands

I: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]
O: 1

• We check our base case if no grid exists
• Initialize our island count to 0 to keep track
• Double for loop to iterate over our nxm grid
  • Check if a grid item is a 1
  • If it is we call our depth-first search helper function - dfs()
    • We pass it our grid and our i and j position
    • Then we increase our count by 1 because we encournted an “island”
• Within the dfs() function we’ve passed it out grid, i, and j so we:
  • Check if we’re within range our our grid, and that we’re searching for other islands (1’s) with an if statement:
    • if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]!='1':
  • After that check we set the current grid item from 1 to 0
  • Then we recursively called our dfs() function in all 4 directions:
    • right = grid,i+1,j
    • left = grid,i-1,j
    • up = grid,i,j+1
    • down = grid,i,j-1

def numIslands(self, grid: List[List[str]]) -> int:
  if not grid:
      return 0

  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,i,j):
  if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j]!='1':
    return
  grid[i][j] = '0'
  self.dfs(grid,i+1,j)
  self.dfs(grid,i-1,j)
  self.dfs(grid,i,j+1)
  self.dfs(grid,i,j-1)

51. N-Queens

I: N = 4
O: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

• We check our base case if no grid exists

Written by Christian Turner
Follow me on Twitter

• ← Strings
• Backtracking →