PROBLEM LINK:
Author: Varun Singh
DIFFICULTY:
EASY
PREREQUISITES:
Graph, Graph-Traversal, DFS
PROBLEM:
Given a binary matrix of size N x M, determine the number of cells in the largest region of the matrix (denoted by 1’s)
EXPLANATION:
Treat the grid as a graph where each cell with a 1 is connected to another cell with a 1 as long as they adjacent horizontally, vertically, or diagonally. Recall that cell [i][j] is adjacent to cells [i±1][j±1] as long as such a cell exists within the confines of the matrix.
Use a standard Depth-First Search (DFS) algorithm but modify it to assign a unique number to each cell identified in a connected component. Because the cells are originally numbered with either a 0 or a 1 but the only cells we care about visiting contain a 1, we just have to mark each cell we visit during our search with some number other than a 1 (e.g. -1, 0, etc.). If you do not wish to modify the values of the original array, you could also maintain another matrix of boolean values tracking whether or not each cell was visited.
Finally, keep a running maximum of the number of connected cells found by each DFS. Once the entire matrix has been searched, print this running maximum.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.