algoadvance

Clarifying Questions

1. Input Format:
   • What is the format of the input? Is it a list of lists, where each sublist represents a row in the grid?
   • Are we guaranteed that the input grid will contain only ‘1’s (land) and ‘0’s (water)?
2. Edge Cases:
   • How should we handle an empty grid?
   • Is the grid guaranteed to be rectangular (all rows have the same number of columns)?
3. Output Format:
   • What should the function return? The number of islands as an integer?

Strategy

The problem can be thought of as finding all connected components in a graph. Here, our graph vertices are the cells of the grid, and edges exist between horizontally and vertically adjacent land cells (‘1’s).

Steps:

1. Traversal:
   • We’ll traverse each cell in the grid.
   • If we encounter a ‘1’, we’ll perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to mark all connected lands as visited.
   • We’ll use a helper method to perform DFS/BFS starting from each ‘1’ it encounters.
2. Marking Visited Cells:
   • During DFS/BFS, we can mark visited cells by setting them to ‘0’ or use an additional visited boolean grid.
3. Counting Islands:
   • Every time we start a DFS/BFS from an unvisited ‘1’, we increment our island count.

Time Complexity

• Time Complexity: O(M x N) where M is the number of rows and N is the number of columns. Each cell is visited once.
• Space Complexity: O(M x N) due to the recursive stack in DFS or the queue in BFS and also potentially the visited array, though we can optimize by marking cells directly in the input grid.

Here’s the implementation in Python using the DFS approach:

Code

def numIslands(grid):
    if not grid:
        return 0

    def dfs(grid, r, c):
        rows, cols = len(grid), len(grid[0])
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
        # Mark this cell as '0' to indicate it's visited
        grid[r][c] = '0'
        # Perform DFS in all 4 directions
        dfs(grid, r + 1, c)
        dfs(grid, r - 1, c)
        dfs(grid, r, c + 1)
        dfs(grid, r, c - 1)

    rows, cols = len(grid), len(grid[0])
    island_count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                island_count += 1
                dfs(grid, r, c)

    return island_count

Edge Cases Considered:

• An empty grid or a grid with no ‘1’s at all.
• A grid with only one row or one column.
• Grids where islands are touching each other only diagonally, which shouldn’t be counted as a single island.

Is there anything specific you’d like to adjust or any other part you’d like to focus on?

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?