2
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ "Nested functions are unusual" – I am not a professional Python programmer, therefore some reference supporting this claim would be appreciated. \$\endgroup\$ – Martin R Aug 22 '18 at 6:54
  • \$\begingroup\$ I would simply recommend reading some Python code. I don't think I've seen anyone use nested functions in Python ever before. \$\endgroup\$ – l0b0 Aug 22 '18 at 9:28
  • 1
    \$\begingroup\$ @l0b0 When writing decorators they are necessary. But otherwise there are usually better ways to achieve what you want (like passing something as an argument). \$\endgroup\$ – Graipher Aug 22 '18 at 11:49
  • \$\begingroup\$ @I0b0 Thanks a lot for your feedback. I have learned a lot. \$\endgroup\$ – wispymisty Aug 24 '18 at 0:52
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That is so cool. I will learn more standard library also. That is one area I need to seriously upgrade. \$\endgroup\$ – wispymisty Aug 24 '18 at 0:52
  • \$\begingroup\$ @wispymisty While I agree that the standard library is very good, this is unfortunately not part of it. \$\endgroup\$ – Graipher Aug 24 '18 at 5:28
0
\$\begingroup\$

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 using a queue (named q). Actually, you are performing a 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)))
\$\endgroup\$
  • \$\begingroup\$ Thank you so much. It shows me how a really pythonic program would work. \$\endgroup\$ – wispymisty Sep 7 '18 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.