Teaching Kids Programming – Depth First Search Algorithm to Find the Largest Land

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional integer matrix of 1s and 0s. A 1 represents land and 0 represents water, so an island is a group of 1s that are neighboring whose perimeter is surrounded by water. You can assume that the edges of the matrix are surrounded by water.

Return the area of the largest island in matrix.

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5 6 7 8

matrix = [     [0, 0, 0, 1, 1, 1, 1],     [0, 0, 0, 0, 0, 0, 0],     [0, 1, 1, 1, 1, 1, 0],     [0, 0, 1, 1, 0, 0, 0],     [0, 0, 0, 0, 0, 1, 1],     [0, 0, 0, 0, 0, 0, 0] ]

matrix = [
    [0, 0, 0, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 0],
    [0, 0, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 0]
]

Output
7
Explanation
The largest island in the center has an area of 7 units.

Depth First Search Algorithm to Find the Largest Island

We can perform a Depth First Search starting a location, making land water once we visit and count it. The DFS will visit neighbour pixels, count and mark the land visited, and return the size of the current land.

Similar to Teaching Kids Programming – Depth First Search Algorithm to Count the Number of Islands, the only difference is that we are returning the size of the current land instead of 1 when we want to count the number of lands.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def solve(self, matrix):
        rows = len(matrix)
        if not rows:
            return 0
        cols = len(matrix[0])
        if not cols:
            return 0
        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols:
                return 0
            if matrix[r][c] == 0:
                return 0
            ans = 1
            matrix[r][c] = 0  # mark as visited
            for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                ans += dfs(r + dx, c + dy)
            return ans
        ans = 0
        for r in range(rows):
            for c in range(cols):
                ans = max(ans, dfs(r, c))
        return ans

class Solution:
    def solve(self, matrix):
        rows = len(matrix)
        if not rows:
            return 0
        cols = len(matrix[0])
        if not cols:
            return 0
        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols:
                return 0
            if matrix[r][c] == 0:
                return 0
            ans = 1
            matrix[r][c] = 0  # mark as visited
            for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                ans += dfs(r + dx, c + dy)
            return ans
        ans = 0
        for r in range(rows):
            for c in range(cols):
                ans = max(ans, dfs(r, c))
        return ans

The time complexity and space complexity is both O(N) where N is the number of the pixels.

Island Problems and Algorithms:

• Teaching Kids Programming – Island Shape Perimeter Algorithm
• Teaching Kids Programming – Depth First Search Algorithm to Count the Number of Islands
• Teaching Kids Programming – Depth First Search Algorithm to Find the Largest Land
• Teaching Kids Programming – Recursive Depth First Search Algorithm to Count the Surrounded Islands

–EOF (The Ultimate Computing & Technology Blog) —