Algorithm

Problem Name: 695. Max Area of Island

Problem Link: https://leetcode.com/problems/max-area-of-island/
 

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.

 

Example 1:

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.

Example 2:

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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;
        int maxArea = 0, m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++)
            for(int j = 0; j  <  n; j++)
                if(grid[i][j]){
                    int area = 0;
                    DFS(grid, i, j, m, n, area, maxArea);
                }
        return maxArea;
    }
    
    void DFS(vector < vector<int>>& grid, int r, int c, int m, int n, int& area, int& maxArea){
        if(r  <  0 || c < 0 || r == m || c == n || grid[r][c] == 0){
            maxArea = max(maxArea, area);
            return;
        }
        area++;
        grid[r][c] = 0;
        DFS(grid, r + 1, c, m, n, area, maxArea);
        DFS(grid, r - 1, c, m, n, area, maxArea);
        DFS(grid, r, c + 1, m, n, area, maxArea);
        DFS(grid, r, c - 1, m, n, area, maxArea>;
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
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

x
–
+
cmd
6

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  private final int[][] DIRS = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
  
  public int maxAreaOfIsland(int[][] grid) {
    int area = 0;
    int rows = grid.length; 
    int cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    for (int i = 0; i  <  rows; i++) {
      for (int j = 0; j  <  cols; j++) {
        if (!visited[i][j] && grid[i][j] == 1) {
          Queue<int[]> queue = new LinkedList<>();
          int currArea = 0;
          queue.add(new int[]{i, j});
          visited[i][j] = true;
          while (!queue.isEmpty()) {
            int[] removed = queue.remove();
            currArea++;
            for (int[] dir : DIRS) {
              int x = removed[0] + dir[0];
              int y = removed[1] + dir[1];
              if (x >= 0 && y >= 0 && x  <  rows && y < cols && !visited[x][y] && grid[x][y] == 1) {
                queue.add(new int[]{x, y});
                visited[x][y] = true;
              }
            }
          }
          area = Math.max(area, currArea);
        }
      }
    }
    return area;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
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

x
–
+
cmd
6

#3 Code Example with Javascript Programming

Code - Javascript Programming


const maxAreaOfIsland = function(grid) {
    let res = 0
    const seen = []
    for(let i = 0; i  <  grid.length; i++) {
        seen[i] = []
    }
    for(let i = 0; i  <  grid.length; i++) {
        for(let j = 0; j  <  grid[0].length; j++) {
            res = Math.max(res, area(i, j, seen, grid))
        }
    }
    return res
};

function area(r, c, seen, grid) {
    console.log(grid)
    if (r  <  0 || r >= grid.length || c < 0 || c >= grid[0].length || seen[r][c] || grid[r][c] == 0) return 0;
    seen[r][c] = true;
    return (1 + area(r+1, c, seen, grid) + area(r-1, c, seen, grid) + area(r, c-1, seen, grid) + area(r, c+1, seen, grid));
}

console.log(maxAreaOfIsland([[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]))
console.log(maxAreaOfIsland([[1,0],[1,1]]))
console.log(maxAreaOfIsland([[1,1],[1,0]]))
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
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

x
–
+
cmd
6

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def maxAreaOfIsland(self, grid):
        m, n = len(grid), len(grid and grid[0])
        def explore(i, j):
            grid[i][j] = 0
            return 1 + sum(explore(x,y) for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)) if 0<=x
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
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

x
–
+
cmd
6

#5 Code Example with C# Programming

Code - C# Programming


using System;

namespace LeetCode
{
    public class _0695_MaxAreaOfIsland
    {
        public int MaxAreaOfIsland(int[][] grid)
        {
            var uf = new UnionFind(grid);

            int m = grid.Length;
            int n = grid[0].Length;
            for (int i = 0; i  <  m; i++)
                for (int j = 0; j  <  n; j++)
                    if (grid[i][j] == 1)
                    {
                        if (i - 1 >= 0 && grid[i - 1][j] == 1)
                            uf.Union(i * n + j, (i - 1) * n + j);
                        if (i + 1  <  m && grid[i + 1][j] == 1)
                            uf.Union(i * n + j, (i + 1) * n + j);
                        if (j - 1 >= 0 && grid[i][j - 1] == 1)
                            uf.Union(i * n + j, i * n + j - 1);
                        if (j + 1  <  n && grid[i][j + 1] == 1)
                            uf.Union(i * n + j, i * n + j + 1);
                    }
            return uf.RankMax();
        }


        public class UnionFind
        {
            private int count = 0;
            private int rankMax = 0;
            private int[] parents;
            private int[] ranks;

            public UnionFind(int[][] grid)
            {
                count = 0;
                int m = grid.Length;
                int n = grid[0].Length;

                parents = new int[m * n];
                ranks = new int[m * n];
                for (int i = 0; i  <  m; i++)
                    for (int j = 0; j  <  n; j++)
                    {
                        if (grid[i][j] == 1)
                        {
                            parents[i * n + j] = i * n + j;
                            count++;
                            ranks[i * n + j] = 1;
                            rankMax = 1;
                        }
                    }
            }

            public int Find(int index)
            {
                if (parents[index] != index)
                    parents[index] = Find(parents[index]);

                return parents[index];
            }

            public void Union(int index1, int index2)
            {
                var pIndex1 = Find(index1);
                var pIndex2 = Find(index2);

                if (pIndex1 != pIndex2)
                {
                    if (ranks[pIndex1] >= ranks[pIndex2])
                    {
                        parents[pIndex2] = pIndex1;
                        ranks[pIndex1] += ranks[pIndex2];
                        rankMax = Math.Max(ranks[pIndex1], rankMax);
                    }
                    else
                    {
                        parents[pIndex1] = pIndex2;
                        ranks[pIndex2] += ranks[pIndex1];
                        rankMax = Math.Max(ranks[pIndex2], rankMax);
                    }
                    count--;
                }
            }

            public int RankMax()
            {
                return rankMax;
            }

            public int Count()
            {
                return count;
            }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
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

x
–
+
cmd
6
Advertisements

Demonstration

Previous
#693 Leetcode Binary Number with Alternating Bits Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#696 Leetcode Count Binary Substrings Solution in C, C++, Java, JavaScript, Python, C# Leetcode