Number of Islands
Statement
Consider an m × n 2D grid that contains binary numbers, where 0 represents water and 1 represents land. If any 1 cells are connected horizontally or vertically (not diagonally), then they form an island. Find the total number of islands in the grid.
Constraints
- 1 ≤
grid.length()≤ 50 - 1 ≤
grid[i].length()≤ 50 grid[i][j]is either0or1
Solution
"""
production algorithm
"""
class Solution:
def number_of_islands(self, grid):
"""
time complexity O(mn)
space complexity O(mn)
"""
water, land = 0, 1
m, n = len(grid), len(grid[0])
unionfind = UnionFind(m * n)
# exlcude water cells
# reduce count of representatives
for row in range(m):
for column in range(n):
if grid[row][column] == water:
unionfind.count -= 1
# union land cells
# reduce count of representatives
for row in range(m):
for column in range(n):
if grid[row][column] == land:
if row < m - 1 and grid[row + 1][column] == land:
unionfind.union(row * n + column,
(row + 1) * n + column)
if column < n - 1 and grid[row][column + 1] == land:
unionfind.union(row * n + column,
row * n + (column + 1))
return unionfind.count
class UnionFind:
def __init__(self, size):
self.parent = [n for n in range(size + 1)]
self.size = [1 for _ in range(size + 1)]
self.count = size
def find(self, x):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
if not self.parent[x] == x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
rootx = self.find(x)
rooty = self.find(y)
if not rootx == rooty:
if self.size[rootx] < self.size[rooty]:
rooty, rootx = rootx, rooty
self.parent[rooty] = rootx
self.size[rootx] += self.size[rooty]
self.count -= 1"""
unit tests
"""
from unittest import TestCase
from algorithms.union_find.number_of_islands.solution import Solution
class SolutionTestCase(TestCase):
def test_number_of_islands(self):
# Given
grid = [[1, 1, 1, 0, 0, 0],
[1, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 0],
[0, 0, 1, 1, 1, 1],
[1, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 1]]
solution = Solution()
# When
actual = solution.number_of_islands(grid)
# Then
expected = 5
self.assertEqual(actual, expected)Strategy
Union Find.
Explanation
Given a grid with m rows and n columns, the algorithm creates a UnionFind with size m × n. Then, the algorithm iterates the cells of the grid twice.
In the first iteration of the cells, the algorithm excludes water cells from the number of representatives of the UnionFind. This is done since the number of representatives represents the number of islands.
Next, in the second iteration of the cells, the algorithm unions land cells. For each union, the number of representatives is reduced by one, since a union means that two land cells belong to the same island.
In the end, the number of representatives is the number of islands.
Time Complexity
Let m be the number of rows and n be the number of columns in the grid. The algorithm iterates all cells of the grid twice. Each iteration operates on the UnionFind whose operations have amortized time complexity O(⍺(m × n)) where ⍺(m × n) is the inverse Ackerman function. Therefore, the time complexity of the algorithm is O(m × n × ⍺(m × n)), or simply O(m × n).
Space Complexity
The UnionFind uses auxiliary space for each cell of the grid. Therefore, the auxiliary space complexity of the algorithm is O(m × n).
