Find maximum area of island in matrix

Question

I recently solved the problem below from leetcode:

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical). Find the maximum area of an island in the given 2D array.

This is how I normally write python code. I am thinking this might not be really Pythonic. Please help review the code.

from operator import add


def max_area_of_island(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    rlen = len(grid)
    clen = len(grid[0])

    visited = [[0] * clen for _ in range(rlen)]
    max_island = 0
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def add_dir(cur_loc, d):
        cur_i, cur_j = cur_loc
        new_i, new_j = tuple(map(add, cur_loc, d))
        if new_i >= 0 and new_i < rlen and new_j >= 0 and new_j < clen:
            #print("all good")
            return new_i, new_j
        #print("error")
        return -1, -1

    max_area = 0
    for i in range(rlen):
        for j in range(clen):
            if grid[i][j] == 0 or visited[i][j]:
                continue
            area = 1
            q = [(i,j)]
            visited[i][j] = True
            #print("before qsize", q.qsize())
            while q:
                #print("during qsize", q.qsize())
                cur = q.pop()
                for _,d in enumerate(dirs):
                    new_i, new_j = add_dir(cur, d)
                    if new_i < 0 or visited[new_i][new_j]: continue
                    if new_i >= 0 and grid[new_i][new_j]:
                        new_loc = (new_i, new_j)
                        q.append(new_loc)
                        visited[new_i][new_j] = True
                        area += 1
            max_area = max(area, max_area)

    return max_area

Answer 1

Some suggestions:

• Nested functions are unusual; typically they would be neighbour functions instead. This ensures that all the context that each function needs is passed to it, making it easier to grasp the entire context involved in the processing in each function.

• Python 3 supports type annotations, which are a more explicit way of declaring input and output types. You can check that your code is properly annotated using mypy, for example with this rather strict configuration:

  [mypy]
  check_untyped_defs = true
  disallow_untyped_defs = true
  ignore_missing_imports = true
  no_implicit_optional = true
  warn_redundant_casts = true
  warn_return_any = true
  warn_unused_ignores = true
  

• Longer variable names can make your code more readable. For example, I can't tell what q is without reading most of the code, and even then it might be unclear, especially since it's an "intermediate" variable (neither a parameter nor a return value).
• You could use a set of constants to define the directions in a more human readable form such as DIRECTION_WEST = (-1, 0).
• Inlining such as if foo: continue is generally frowned upon, since it makes it harder to skim the code vertically.
• Your docstring could include a definition of the problem, possibly by simply copying from the LeetCode website.
• Python has exceptions, and it's recommended to use them rather than special return values to signal a problem.

Answer 2

If you were trying to solve this problem in real life (and not on leetcode), I would use existing tools for this. Specifically, with scikit-image this becomes rather easy:

import numpy as np
from skimage import measure

def largest_island(grid):
    labels = measure.label(grid, connectivity=1)
    return max(region.area for region in measure.regionprops(labels))

if __name__ == "__main__":
    grid = np.array([[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]])
    print(largest_island(grid))

This uses skimage.measure.label to give each connected area a unique label, where areas can only be connected horizontally and vertically, but not diagonally. It then uses skimage.measure.regionprops, which calculates properties of labeled regions.

Unfortunately, scikit-image seems not to be included on leetcode.

Answer 3

Your code is somewhat Pythonic, but could use some improvements.

You seem to be under the impression that you are exploring each island by performing a breadth-first-search using a queue (named q). Actually, you are performing a depth-first-search using a stack. (You can't .pop() a queue!)

for _,d in enumerate(dirs) is a pointless use of enumerate(), and it should be written as for d in dirs.

If you name the bounds as rlen and clen, then I would prefer that you use r and c (instead of i and j) for your coordinates.

Your add_dir() function is a bit clumsy. You return (-1, -1) if the result is out of bounds, which means that the caller also has to check whether the result is out of bounds. What you want is a neighbors(r, c) function that lists all of the neighbor coordinates of (r, c) that are in bounds. One Pythonic technique that you can use is to write it as a generator. Another trick is to use chained comparisons (e.g. x < y <= z).

It's a bit uncouth to initialize the elements of visited to 0, then set some of them to True, mixing integers with booleans.

A more readable way to express the goal of the max_area_of_island() function would be:

return max(island_size(r, c) for r, c in product(range(rlen), range(clen)))

… taking advantage of itertools.product() to avoid a nested loop. I have therefore reorganized the code to provide an island_size() function to enable that.

from itertools import product

def max_area_of_island(grid):
    rlen, clen = len(grid), len(grid[0])
    def neighbors(r, c):
        """
        Generate the neighbor coordinates of the given row and column that
        are within the bounds of the grid.
        """
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if (0 <= r + dr < rlen) and (0 <= c + dc < clen):
                yield r + dr, c + dc

    visited = [[False] * clen for _ in range(rlen)]
    def island_size(r, c):
        """
        Find the area of the land connected to the given coordinate.
        Return 0 if the coordinate is water or if it has already been
        explored in a previous call to island_size().
        """
        if grid[r][c] == 0 or visited[r][c]:
            return 0
        area = 1
        stack = [(r, c)]
        visited[r][c] = True
        while stack:
            for r, c in neighbors(*stack.pop()):
                if grid[r][c] and not visited[r][c]:
                    stack.append((r, c))
                    visited[r][c] = True
                    area += 1
        return area

    return max(island_size(r, c) for r, c in product(range(rlen), range(clen)))