Graph: Given a binary matrix, find the largest region of 1

Problem Statement:

You are given a binary matrix, you need to find the maximum region of 1, that can be connected in 4 directions.

The edges of the matrix assumed to be surrounded by water

Example:

Input: M[][]= {{1, 0, 0, 0},
               {0, 1, 0, 0},
               {1, 1, 0, 0},
               {1, 0, 0, 1}}

Output: 5

Solution Explanation:

We will solve the issue with DFS.

If any value of the cell is 1, then we will check and add the area of corresponding cells.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void computeArea(vector<vector<int>>& grid, int i, int j, int& a) 
{
    int m = grid.size(), n = grid[0].size();

    if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j]) 
    {
        a++;
        grid[i][j] = 0;            
        computeArea(grid, i - 1, j, a); // up
        computeArea(grid, i + 1, j, a); // down
        computeArea(grid, i, j - 1, a); // left
        computeArea(grid, i, j + 1, a); // right
    }
}


int solution(vector<vector<int>>& grid) 
{
    int m = grid.size(); //rows
    int n =  grid[0].size(); //columns
    int area = 0;

    for (int i = 0; i < m; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            if (grid[i][j]) 
            {
                int a = 0;
                computeArea(grid, i, j, a);
                area = max(area, a);
            }
        }
    }
    return area;
}

int main() 
{
    vector<vector<int>> grid = {{1, 0, 0, 0},
               				 {0, 1, 0, 0},
               				 {1, 1, 0, 0},
               				 {1, 0, 0, 1}};

    cout << solution(grid);

    return 0;
}

Output

4