Number of Islands


  1. Clarify the problem:

    • The problem requires us to count the number of islands in a given 2D grid.
    • An island is represented by a group of connected '1's (representing land) surrounded by '0's (representing water).
    • We need to implement a function that takes in the grid as input and returns the number of islands.
  2. Analyze the problem:

    • Input: 2D grid of characters.
    • Output: Number of islands (integer).
    • Constraints:
      • The grid can have '0's and '1's only.
      • An island is formed by connecting horizontally or vertically adjacent '1' cells.
      • Diagonal connections are not considered.
      • The grid size is between 1 and 10^4.
  3. Design an algorithm:

    • We can solve this problem using a depth-first search (DFS) approach.
    • The idea is to traverse the grid and explore each cell to find the connected island cells.
    • We can define a recursive function to perform the DFS.
    • The function will take the current cell coordinates as input.
    • If the current cell is valid (within the grid bounds) and represents land ('1'), we mark it as visited and recursively call the function on its neighboring cells.
    • We mark the visited cells to avoid counting them again.
    • Each time we encounter a new unvisited island cell ('1'), we increment the island count.
    • Finally, we iterate over the entire grid, calling the DFS function on each unvisited island cell, and return the total island count.
  4. Explain your approach:

    • We will implement a depth-first search (DFS) algorithm to count the number of islands.
    • First, we define a recursive function dfs that takes the current cell coordinates as input.
    • Inside the function, we check if the current cell is valid and represents land ('1').
    • If it is, we mark it as visited by updating its value to '0'.
    • Then, we recursively call the dfs function on the neighboring cells (up, down, left, and right).
    • After defining the dfs function, we initialize a variable island_count to 0.
    • Next, we iterate over the grid and call the dfs function on each unvisited island cell ('1').
    • Each time we encounter a new unvisited island cell, we increment the island_count.
    • Finally, we return the island_count.
  5. Write clean and readable code:

  6. class Solution: def numIslands(self, grid): def dfs(i, j): if 0 <= i < rows and 0 <= j < cols and grid[i][j] == '1': grid[i][j] = '0' dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) rows = len(grid) cols = len(grid[0]) island_count = 0 for i in range(rows): for j in range(cols): if grid[i][j] == '1': island_count += 1 dfs(i, j) return island_count solution = Solution() grid = [['1', '1', '1', '1', '0'], ['1', '1', '0', '1', '0'], ['1', '1', '0', '0', '0'], ['0', '0', '0', '0', '0']] num_islands = solution.numIslands(grid) print(num_islands) # Output: 1
  7. Test your code:

    • We test the code with a grid containing a single island.
    • We chose this test case to ensure that the code can correctly identify and count a single island.
    • We expect the output to be 1, as there is only one island in the given grid.
  8. Optimize if necessary:

    • The provided solution already uses the most efficient approach to solve the problem, which is DFS.
    • There are no further optimizations needed for this solution.
  9. Handle error cases:

    • The code assumes that the input grid is a valid 2D list containing only '0's and '1's.
    • If the input is empty or the grid size is outside the constraints, the behavior of the code may be undefined.
  10. Discuss complexity analysis:

    • Let M be the number of rows and N be the number of columns in the grid.
    • The time complexity of the solution is O(M*N) as we visit each cell of the grid exactly once.
    • The space complexity is O(M*N) in the worst case, considering the recursive stack space used by the DFS algorithm.
    • The solution is efficient and performs well for grids with a large number of cells.
Next Post Previous Post