Leetcode: number of islands I am on my second iteration of the famous &quot;Number Of Islands&quot; 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 = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
Output: 1

Example 2:

Input: grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
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]]) -&gt; int:
        &quot;&quot;&quot;
        Gets the neighbors of a coordinate in a grid. Returns a list of tuples.
        &quot;&quot;&quot;
        m = len(grid)
        n = len(grid[0])

        def get_neighbors(coord: Tuple[int, int]) -&gt; 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 &lt; new_x &lt; m and -1 &lt; new_y &lt; 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]] == &quot;1&quot;:
                    islands += 1

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

        return islands
My suggestions:

The variables m and n are initialized but never used

The function get_neighbors:
def get_neighbors(coord: Tuple[int, int]) -&gt; 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 &lt; new_x &lt; m and -1 &lt; new_y &lt; n:
            neighbors.append((new_x, new_y))

    return neighbors

Can be simplified to:
def get_neighbors(r: int, c: int) -&gt; 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 &lt; r &lt; m and -1 &lt; c &lt; 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]]) -&gt; int:
    islands = 0
    m, n = len(grid), len(grid[0])

    def sink_neighbors(row, col):
        grid[row][col] = '0'
        if row &gt; 0 and grid[row - 1][col] == '1':
            sink_neighbors(row - 1, col)
        if row &lt; m - 1 and grid[row + 1][col] == '1':
            sink_neighbors(row + 1, col)
        if col &gt; 0 and grid[row][col - 1] == '1':
            sink_neighbors(row, col - 1)
        if col &lt; 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]]) -&gt; int:
    m = len(grid)
    n = len(grid[0])

    def get_neighbors(coord: Tuple[int, int]) -&gt; 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 &lt; new_x &lt; m and -1 &lt; new_y &lt; 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]] == &quot;1&quot;:
                islands += 1
                q = deque([coord])
                while len(q) &gt; 0:
                    c = q.popleft()
                    grid[c[0]][c[1]] = &quot;0&quot;
                    for neighbor in get_neighbors(c):
                        if grid[neighbor[0]][neighbor[1]] == &quot;1&quot;:
                            q.append(neighbor)
                            grid[neighbor[0]][neighbor[1]] = &quot;0&quot;

    return islands


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

    def get_neighbors(r: int, c: int) -&gt; 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 &lt; r &lt; m and -1 &lt; c &lt; n]

    islands = 0

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

    return islands


def improved2(grid: List[List[str]]) -&gt; 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 &lt;= r &lt; m and 0 &lt;= c &lt; n and grid[r][c] == '1':
                            grid[r][c] = '0'
                            q.append((r, c))
    return islands


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

    def sink_neighbors(row, col):
        grid[row][col] = '0'
        if row &gt; 0 and grid[row - 1][col] == '1':
            sink_neighbors(row - 1, col)
        if row &lt; m - 1 and grid[row + 1][col] == '1':
            sink_neighbors(row + 1, col)
        if col &gt; 0 and grid[row][col - 1] == '1':
            sink_neighbors(row, col - 1)
        if col &lt; 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__ == &quot;__main__&quot;:
    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)