Leetcode: number of islands

Question

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

Answer 1

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)

Answer 2

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]: