LeetCode 695. Max Area of Island

December 11, 2020

We can treat the matrix as a graph, with each 1 representing a vertex and each shared edge representing a graph edge. If we do a DFS from each vertex, we can find all connected components of the graph. These connected components correspond to islands.

The runtime of this algorithm is $O(n)$ if we keep a top-level set of seen vertices so we run at most one DFS per connected component.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.maxAreaOfIsland(
            [[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]]
        ), 6)
        self.assertEqual(self.s.maxAreaOfIsland([[0,0,0,0,0,0,0,0]]), 0)

    def test_empty(self):
        self.assertEqual(self.s.maxAreaOfIsland([]), 0)
        self.assertEqual(self.s.maxAreaOfIsland([[]]), 0)
        self.assertEqual(self.s.maxAreaOfIsland([[],[]]), 0)

    def test_zero(self):
        self.assertEqual(self.s.maxAreaOfIsland([[0]]), 0)
        self.assertEqual(self.s.maxAreaOfIsland([[0],[0]]), 0)

class Solution:

    def _findConnectedSize(self, i: int, j: int, grid: List[List[int]], seen: set) -> int:
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[i]):
            return 0
        if grid[i][j] == 0 or (i,j) in seen:
            return 0
        seen.add((i,j))
        size = 1
        for iN,jN in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
            size += self._findConnectedSize(iN, jN, grid, seen)
        return size

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_area = 0
        seen = set()
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                max_area = max(max_area, self._findConnectedSize(i, j, grid, seen))
        return max_area

if __name__ == "__main__":
    unittest.main()