Count Islands in a Binary Grid

Question

The question asks the candidate to implement an algorithm that counts the number of islands in a given binary grid, where '1' represents land and '0' represents water.

Codemia · Accepted Answer

To count the number of islands in a binary grid, we can use Depth-First Search (DFS) or Breadth-First Search (BFS). The idea is to traverse the grid and, whenever we encounter a '1', we initiate a search to mark all connected '1's (land) as visited. Each initiation of a search corresponds to discovering a new island. We can implement the algorithm as follows: 1. Initialize a counter to keep track of the number of islands. 2. Loop through each cell in the grid. 3. If a cell contains '1', increment the counter and perform a DFS/BFS to mark all connected '1's as '0' (or visited). 4. Continue until all cells have been processed. Here is a sample implementation in Python: ```python def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) count = 0 def dfs(r, c): if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0': return grid[r][c] = '0' # mark as visited dfs(r - 1, c) # up dfs(r + 1, c) # down dfs(r, c - 1) # left dfs(r, c + 1) # right for r in range(rows): for c in range(cols): if grid[r][c] == '1': count += 1 dfs(r, c) return count ``` The time complexity of this algorithm is O(M * N), where M is the number of rows and N is the number of columns in the grid. This is because in the worst case, we may visit every cell in the grid. The space complexity is O(M * N) in the case of recursion stack for DFS, or O(min(M, N)) for BFS using a queue. Consider edge cases such as: - An empty grid, which should return 0. - A grid with no land (all '0's), which should also return 0. - A grid that is entirely land (all '1's), which should return 1. Interviewers are looking for clarity in the explanation of the approach, the ability to write clean and efficient code, and a solid understanding of time and space complexity. They also appreciate candidates who can think critically about edge cases and potential optimizations.

Count Islands in a Binary Grid

Visa

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Visa Software Engineer I Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string