4
\$\begingroup\$

I am on my second iteration of the famous "Number Of Islands" graph problem on Leetcode.

https://leetcode.com/problems/number-of-islands/

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

My approach is to iterate through each cell in the grid, incrementing a counter when the value == 1. Then, do a breadth-first search of the cell's neighbors, adding them to the queue if their value == 1. Once the queue is empty, keep iterating through all the cells.

To avoid infinite loops, I first used a set() to keep track of a list of tuple coordinates. This seemed to jack up my memory usage, so I then improved the algorithm by removing the set and simply setting the value of visited cells to 0.

I passed all the test cases but still can't figure out how to get a better runtime. I'm currently slower than ~90% of python submissions.

I would appreciate if anyone can help speed this thing up!


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
        Gets the neighbors of a coordinate in a grid. Returns a list of tuples.
        """
        m = len(grid)
        n = len(grid[0])

        def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:
            delta_row    = [0, 1, 0, -1]
            delta_column = [1, 0, -1, 0]

            neighbors = []
            for i in range(len(delta_row)):
                new_x = coord[0] + delta_row[i]
                new_y = coord[1] + delta_column[i]

                if -1 < new_x < m and -1 < new_y < n:
                    neighbors.append((new_x, new_y))

            return neighbors

        # loop through the entire grid and set coords to 0 as we visit them 
        # if val == 1, do a breadth-first search for neighbors and increment islands
        # if val == 0, continue to next coordinate.

        islands = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                coord = (i, j)
                if grid[coord[0]][coord[1]] == "1":
                    islands += 1

                    # breadth-first search
                    q = deque([coord])
                    while len(q) > 0:
                        c = q.popleft()
                        grid[c[0]][c[1]] = "0"
                        for neighbor in get_neighbors(c):
                            if grid[neighbor[0]][neighbor[1]] == "1":
                                q.append(neighbor)
                                grid[neighbor[0]][neighbor[1]] = "0"

        return islands
\$\endgroup\$
2
3
\$\begingroup\$

My suggestions:

  • The variables m and n are initialized but never used

  • The function get_neighbors:

    def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:
        delta_row    = [0, 1, 0, -1]
        delta_column = [1, 0, -1, 0]
    
        neighbors = []
        for i in range(len(delta_row)):
            new_x = coord[0] + delta_row[i]
            new_y = coord[1] + delta_column[i]
    
            if -1 < new_x < m and -1 < new_y < n:
                neighbors.append((new_x, new_y))
    
        return neighbors
    

    Can be simplified to:

    def get_neighbors(r: int, c: int) -> List[Tuple]:
        neighbors = (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)
        return [(r, c) for r, c in neighbors if -1 < r < m and -1 < c < n]
    

    Instead of unpacking coord you can pass the row r and column c directly. This also improves the runtime by roughly 30%.

Alternative approach

An alternative and faster approach is to use recursion:

def recursive(grid: List[List[str]]) -> int:
    islands = 0
    m, n = len(grid), len(grid[0])

    def sink_neighbors(row, col):
        grid[row][col] = '0'
        if row > 0 and grid[row - 1][col] == '1':
            sink_neighbors(row - 1, col)
        if row < m - 1 and grid[row + 1][col] == '1':
            sink_neighbors(row + 1, col)
        if col > 0 and grid[row][col - 1] == '1':
            sink_neighbors(row, col - 1)
        if col < n - 1 and grid[row][col + 1] == '1':
            sink_neighbors(row, col + 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                islands += 1
                sink_neighbors(r, c)
    return islands

Running the recursive solution on LeetCode:

Runtime: 120 ms, faster than 98.12% of Python3 online submissions for Number of Islands

This is the running time of the original, improved, and recursive solutions on a random grid of 1 million elements:

Runtime original: 2.345 s
Runtime improved: 1.544 s
Runtime improved2: 1.097 s
Runtime recursive: 0.696 s

Full code

from collections import deque
from typing import List, Tuple
import random
from time import perf_counter as pc


def original(grid: List[List[str]]) -> int:
    m = len(grid)
    n = len(grid[0])

    def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:
        delta_row = [0, 1, 0, -1]
        delta_column = [1, 0, -1, 0]

        neighbors = []
        for i in range(len(delta_row)):
            new_x = coord[0] + delta_row[i]
            new_y = coord[1] + delta_column[i]

            if -1 < new_x < m and -1 < new_y < n:
                neighbors.append((new_x, new_y))

        return neighbors

    islands = 0

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            coord = (i, j)
            if grid[coord[0]][coord[1]] == "1":
                islands += 1
                q = deque([coord])
                while len(q) > 0:
                    c = q.popleft()
                    grid[c[0]][c[1]] = "0"
                    for neighbor in get_neighbors(c):
                        if grid[neighbor[0]][neighbor[1]] == "1":
                            q.append(neighbor)
                            grid[neighbor[0]][neighbor[1]] = "0"

    return islands


def improved(grid: List[List[str]]) -> int:
    m, n = len(grid), len(grid[0])

    def get_neighbors(r: int, c: int) -> List[Tuple]:
        neighbors = (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)
        return [(r, c) for r, c in neighbors if -1 < r < m and -1 < c < n]

    islands = 0

    for row in range(m):
        for col in range(n):
            if grid[row][col] == "1":
                islands += 1
                q = deque([(row, col)])
                while len(q) > 0:
                    r, c = q.popleft()
                    grid[r][c] = "0"
                    for r, c in get_neighbors(r, c):
                        if grid[r][c] == "1":
                            q.append((r, c))
                            grid[r][c] = "0"

    return islands


def improved2(grid: List[List[str]]) -> int:
    m, n = len(grid), len(grid[0])
    islands = 0
    for row in range(m):
        for col in range(n):
            if grid[row][col] == '1':
                islands += 1
                grid[row][col] = '0'
                q = [(row, col)]
                while q:
                    r, c = q.pop(0)
                    for r, c in (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1):
                        if 0 <= r < m and 0 <= c < n and grid[r][c] == '1':
                            grid[r][c] = '0'
                            q.append((r, c))
    return islands


def recursive(grid: List[List[str]]) -> int:
    islands = 0
    m, n = len(grid), len(grid[0])

    def sink_neighbors(row, col):
        grid[row][col] = '0'
        if row > 0 and grid[row - 1][col] == '1':
            sink_neighbors(row - 1, col)
        if row < m - 1 and grid[row + 1][col] == '1':
            sink_neighbors(row + 1, col)
        if col > 0 and grid[row][col - 1] == '1':
            sink_neighbors(row, col - 1)
        if col < n - 1 and grid[row][col + 1] == '1':
            sink_neighbors(row, col + 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                islands += 1
                sink_neighbors(r, c)
    return islands


if __name__ == "__main__":
    N = 1000
    random_grid = [[str(random.randint(0, 1)) for _ in range(N)] for _ in range(N)]
    res = []

    # Benchmark
    for f in original, improved, improved2, recursive:
        random_grid_copy = [row[:] for row in random_grid]
        t0 = pc()
        res.append(f(random_grid_copy))
        t1 = pc()
        print(f'Runtime {f.__name__}: {round(t1 - t0, 3)} s')

    # Correctness
    assert all(x == res[0] for x in res)

\$\endgroup\$
4
  • \$\begingroup\$ It may be worth noting that the recursive flood fill breaks if an island is too large. A 32x32 grid filled with "1"s (i.e. one big island) is sufficient to hit python's default maximum recursion depth of 1000. I really wonder why they didn't include this trivial test case. The OP's iterative flood fill, while a bit slower, is more robust in that regard. \$\endgroup\$ – danzel Mar 28 at 16:09
  • \$\begingroup\$ Great answer, thank you. To sum up, the biggest performance improvement comes from passing coordinates as integers directly to get_neighbors() as opposed to using/unpacking a tuple? Crazy to me that one fix cuts runtime by 30%. Also, the recursive function's base condition is "no neighbors that equal 1", which is an interesting case I'd never considered. This is a very helpful answer, thanks again. \$\endgroup\$ – qotsa42 Mar 28 at 18:57
  • \$\begingroup\$ @qotsa42 I am glad I could help. Less unpacking helps but using list comprehension and doing fewer operations in get_neighbors() also help to get to the 30% improvement. You can try to add changes to the original and run the benchmark to see the difference. \$\endgroup\$ – Marc Mar 29 at 2:54
  • \$\begingroup\$ @qotsa42 FYI I added improved2 that improves the original runtime a bit more \$\endgroup\$ – Marc Mar 29 at 22:56
2
\$\begingroup\$

As performance improvements have already been provided, I want to add some points regarding readability and "pythonic" code.

Variable naming:

m = len(grid)
n = len(grid[0])
...
for i in range(len(grid)):
    for j in range(len(grid[0])):

These variable names are not descriptive at all. The following is way more readable:

height = len(grid)
width = len(grid[0])
...
for row in range(height):
    for column in range(width):

Please also note that we do not need to recalculate these values for our for-loops.


Pythonic while-loop:

while len(q) > 0: is equivalent to while q:.


get_neighbors:

delta_row = [0, 1, 0, -1]
delta_column = [1, 0, -1, 0]
...
for i in range(len(delta_row)):
    new_x = coord[0] + delta_row[i]
    new_y = coord[1] + delta_column[i]

In Python you should basically never have to iterate over an index and access list elements by that index. A quick fix is the following:

delta_rows = [0, 1, 0, -1]
delta_columns = [1, 0, -1, 0]
...
for delta_row, delta_column in zip(delta_rows, delta_columns):
    new_x = coord[0] + delta_row
    new_y = coord[1] + delta_column

Please also note that this is where variable naming is very important to make it easier to read the code and identify mistakes. In get_neighbors you mix three different ways to name your variables (m, n - row, column - x, y) that have to be interpreted by the reader before understanding (and maybe debugging) the code. At first glance it's not obvious to the reader whether new_x should actually be the new row (I'd say the other way round is more intuitive: y = row and x = column) and whether it's correct to compare it to m instead of n.


Conditions:

if -1 < new_x < m and -1 < new_y < n:

can also be written as

if new_x in range(m) and new_y in range(n):

or even better as

if new_row in range(height) and new_column in range(width):

I would argue this further increases readability in this case, although it's up to a bit of personal preference.


Passing around coordinates:

I often find it useful to use collections.namedtuples as "mini-classes" if a certain structure is used often. As you have to pass around and access coordinates quite frequently, this might be applicable here.

By using something like

Coordinate = namedtuple("Coordinate", "row column")

you are then able to create and access coordinates in a more readable way. Example usage:

coordinate = Coordinate(row=row, column=column)
                
row, column = coordinate
row = coordinate.row
column = coordinate.column

grid[coordinate.row][coordinate.column] = "0"

This also applies to type hints in method headers. For example in get_neighbors:

def get_neighbors(coord: Tuple[int, int]) -> List[Tuple]:

becomes

def get_neighbors(coord: Coordinate) -> List[Coordinate]:
\$\endgroup\$
2
  • \$\begingroup\$ These are great tips -- never really seen a use case in the wild for namedtuples, so thanks for pointing that out. So with zip(). Your naming conventions also make much more sense. I appreciate the hints towards being more pythonic. Interestingly, iterating through range(height) and range(width) in get_neighbors() slows down the runtime on larger grids. On the leetcode testcases, using range() takes about 25% longer than doing -1 < x < height. \$\endgroup\$ – qotsa42 Mar 28 at 20:35
  • \$\begingroup\$ m and n are standard names used exactly like that. \$\endgroup\$ – Manuel Mar 29 at 12:52

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.