Max Area Of Island Array

PROBLEM

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example1

*Input*: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
*Output*: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example2

*Input*: grid = [ [0,0,0,0,0,0,0,0] ]
*Output*: 0

Constraints

  • m==grid.length
  • n==grid[i].length
  • 1<=m, n<=50
  • grid[i][j] is either 0 or 1.

SOLVING

we’ll use Depth-first Search method

Steps

  • Parkour the all grid:
    • Next if element equal water so 0
    • Launch DFS function:
      • If position is out scope of the grid or equal to 0 return
      • Current size equal 1
      • Increase size by calling the DFS function on the neighboor [ up, down, right, left ]
      • Return the size
    • Update maxArea if inferior of current island size

Code

class Solution {
public:
  int maxAreaOfIsland(vector<vector<int>> &grid) {
    maxArea = 0;
    m = grid.size();
    n = grid[0].size();
    for (int r = 0; r < m; r++) {
      for (int c = 0; c < n; c++) {
	if (grid[r][c] == 0)
	  continue;

	int islandArea = getIslandArea(grid, r, c);
	maxArea = max(islandArea, maxArea);
      }
    }

    return maxArea;
  }

private:
  int m;
  int n;
  int maxArea;

  int getIslandArea(vector<vector<int>> &grid, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1)
      return 0;

    int size = 1;
    grid[r][c] = 0;

    size += getIslandArea(grid, r + 1, c);
    size += getIslandArea(grid, r - 1, c);
    size += getIslandArea(grid, r, c + 1);
    size += getIslandArea(grid, r, c - 1);

    return size;
  }
};