DFS on grid

Question

Implement a Depth-First Search (DFS) algorithm to traverse a 2D grid represented as a matrix of characters. Given a starting point, your task is to explore all connected cells that share the same character and return the total count of cells visited during the traversal. The input will be a grid of characters and the output should be an integer representing the number of cells visited.

Codemia · Accepted Answer

The problem is to perform a Depth-First Search (DFS) on a 2D grid of characters, starting from a specific point, and count all connected cells that share the same character. The DFS algorithm is suitable here because it allows us to explore all possible paths (in this case, all connected cells) from the starting point recursively. The grid can be thought of as a graph where each cell is a node, and edges exist between horizontally and vertically adjacent nodes that share the same character. 1. **Input Validation**: Ensure the grid is not empty and the starting coordinates are within bounds. 2. **DFS Implementation**: Create a recursive function that will: - Check if the current cell is out of bounds or if it does not match the target character. - Mark the cell as visited (to avoid counting it again) - Recursively call the DFS function for all four possible directions (up, down, left, right). 3. **Count Cells**: Maintain a counter to keep track of the number of cells visited during the traversal. For example, if we have a grid like this: ``` [['A', 'A', 'B'], ['A', 'A', 'B'], ['B', 'B', 'A']] ``` Starting from (0, 0) (which contains 'A'), the DFS will visit the cells (0, 0), (0, 1), (1, 0), and (1, 1), resulting in a count of 4. Here is the Python implementation of the DFS algorithm for the problem: ```python def dfs_count(grid, x, y, target_char, visited): if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or visited[x][y] or grid[x][y] != target_char: return 0 visited[x][y] = True count = 1 # Count this cell # Explore all four directions count += dfs_count(grid, x + 1, y, target_char, visited) count += dfs_count(grid, x - 1, y, target_char, visited) count += dfs_count(grid, x, y + 1, target_char, visited) count += dfs_count(grid, x, y - 1, target_char, visited) return count def count_connected_cells(grid, start_x, start_y): if not grid or not grid[0]: return 0 target_char = grid[start_x][start_y] visited = [[False] * len(grid[0]) for _ in range(len(grid))] return dfs_count(grid, start_x, start_y, target_char, visited) ``` This implementation defines a helper function `dfs_count` to do the recursive DFS, while the main function `count_connected_cells` initializes the process. The time complexity of the DFS algorithm is O(N * M), where N is the number of rows and M is the number of columns in the grid. In the worst case, we may need to visit every cell in the grid if they are all connected. The space complexity is O(N * M) as well, due to the `visited` matrix, which could potentially store a boolean for each cell. Additionally, the recursive call stack may go as deep as the number of cells in the grid in case of a highly connected area. 1. **Empty Grid**: If the grid is empty, the function should return 0. 2. **Single Cell Grid**: If the grid has only one cell, the count should be 1 if the starting point is valid. 3. **Out of Bounds Start**: If the starting point is out of the grid bounds, the function should return 0. 4. **All Cells Different**: If the grid has all different characters, the count should be 1 if the starting point is valid, otherwise 0. 5. **All Cells Same**: If all cells are the same character, the count should equal the total number of cells in the grid.

DFS on grid

Coinbase

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

Coinbase 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