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

GD Star Rating