Count connected components in grid

Question

Given a 2D grid consisting of 0s and 1s, where 1 represents land and 0 represents water, write a function to count the number of connected components of land. A connected component is defined as a group of adjacent 1s that are connected horizontally or vertically. The function should take the grid as input and return the total count of connected components.

Codemia · Accepted Answer

To solve the problem of counting connected components in a 2D grid, we can identify that this is a classic graph traversal problem. Each `1` in the grid represents a land cell, and we need to find all the connected land cells. Since connections are only horizontal or vertical (not diagonal), we can use either Depth First Search (DFS) or Breadth First Search (BFS) to explore all the land cells in a connected component. This makes the traversal approach suitable for this problem. 1. **Initialize Variables**: Start by defining a count variable to track the number of connected components, and a visited set to keep track of which cells have been explored. 2. **Iterate Through the Grid**: Loop through each cell in the grid. If you encounter a `1` that hasn't been visited, it signifies a new connected component. 3. **Perform DFS/BFS**: Initiate a DFS/BFS from this cell to mark all reachable `1`s as visited. 4. **Increment Component Count**: After completing the DFS/BFS for a component, increment the count variable. 5. **Return Count**: Once all cells have been processed, return the count as the result. **Example**: For the grid: ``` 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 ``` - Starting at (0,0), we find a `1` and perform DFS marking (0,0), (0,1), and (1,1) as visited. Count becomes 1. - Next, at (0,2) we find `0`, then at (1,3) we find `1` and perform DFS marking (1,3) and (2,3). Count becomes 2. - Finally, at (3,0) we find another `1` and mark it, incrementing count to 3. The final output is 3. Here is the Python solution for the problem: ```python def countConnectedComponents(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = set() count = 0 def dfs(r, c): if (r < 0 or r >= rows or c < 0 or c >= cols or (r, c) in visited or grid[r][c] == 0): return visited.add((r, c)) dfs(r + 1, c) # down dfs(r - 1, c) # up dfs(r, c + 1) # right dfs(r, c - 1) # left for r in range(rows): for c in range(cols): if grid[r][c] == 1 and (r, c) not in visited: dfs(r, c) count += 1 return count ``` This function counts the number of connected components accurately. The time complexity of this solution is O(M * N), where M is the number of rows and N is the number of columns in the grid. This is because we potentially visit each cell once during the DFS. The space complexity is O(M * N) as well, due to the storage used for the visited set and the call stack during DFS in the worst case when all cells are `1`. 1. **Empty Grid**: If the input grid is empty (i.e., `[]`), the function should return `0` as there are no components to count. 2. **Single Element**: If the grid has only one element (either `0` or `1`), the function should return `0` or `1` accordingly. 3. **All Water**: A grid filled entirely with `0`s should return `0` since there are no land components. 4. **All Land**: A grid filled entirely with `1`s should return `1` as it is one large connected component.

Count connected components in grid

Supabase

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Supabase Software Engineer 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