Teaching Kids Programming – Island Shape Perimeter Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a two-dimensional integer matrix of 1s and 0s where 0 represents empty cell and 1 represents a block that forms a shape, return the perimeter of the shape. There is guaranteed to be exactly one shape, and the shape has no holes in it.

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

1 2 3 4

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

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

Output
8

Hints:
Try to find how much each 1 contributes to the total perimeter.
Each 1 can contribute at max 4 to the total perimeter.

Algorithm to Compute the Island Shape Perimeter

Each square island contributes to 4 perimeters however if it is connected to another square, we need to subtract 1 common edge (permiter 2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def islandShapePerimeter(self, matrix):
        ans = 0
        rows = len(matrix)
        if 0 == rows:
            return 0
        cols = len(matrix[0])
        if cols == 0:
            return 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    ans += 4
                    if r > 0 and matrix[r-1][c] == 1:                    
                        ans -= 2
                    if c > 0 and matrix[r][c-1] == 1:
                        ans -= 2
        return ans

class Solution:
    def islandShapePerimeter(self, matrix):
        ans = 0
        rows = len(matrix)
        if 0 == rows:
            return 0
        cols = len(matrix[0])
        if cols == 0:
            return 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    ans += 4
                    if r > 0 and matrix[r-1][c] == 1:                    
                        ans -= 2
                    if c > 0 and matrix[r][c-1] == 1:
                        ans -= 2
        return ans

The time complexity is O(RC) where R and C are the rows and columns of the matrix respectively and the space complexity is O(1) constant.

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) —