This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook¶

Problem: Island Perimeter.¶

See the LeetCode problem page.

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16

Constraints¶

Can we assume the inputs are valid?
- No, check for None
Can we assume this fits memory?
- Yes

Test Cases¶

* None -> TypeError
* [[1, 0]] -> 4
* [[0, 1, 0, 0],
   [1, 1, 1, 0],
   [0, 1, 0, 0],
   [1, 1, 0, 0]] -> 16

Algorithm¶

For each cell in the grid:

Check left, right, up, down
- For each check, if we are at the edge or the cell we are checking is land, increment sides

Complexity:

Time: O(rows * cols)
Space: O(1)

Code¶

In [1]:

class Solution(object):

    def island_perimeter(self, grid):
        if grid is None:
            raise TypeError('grid cannot be None')
        sides = 0
        num_rows = len(grid)
        num_cols = len(grid[0])
        for i in range(num_rows):
            for j in range(num_cols):
                if grid[i][j] == 1:
                    # Check left
                    if j == 0 or grid[i][j - 1] == 0:
                        sides += 1
                    # Check right
                    if j == num_cols - 1 or grid[i][j + 1] == 0:
                        sides += 1
                    # Check up
                    if i == 0 or grid[i - 1][j] == 0:
                        sides += 1
                    # Check down
                    if i == num_rows - 1 or grid[i + 1][j] == 0:
                        sides += 1
        return sides

Unit Test¶

In [2]:

%%writefile test_island_perimeter.py
import unittest


class TestIslandPerimeter(unittest.TestCase):

    def test_island_perimeter(self):
        solution = Solution()
        self.assertRaises(TypeError, solution.island_perimeter, None)
        data = [[1, 0]]
        expected = 4
        self.assertEqual(solution.island_perimeter(data), expected)
        data = [[0, 1, 0, 0],
                [1, 1, 1, 0],
                [0, 1, 0, 0],
                [1, 1, 0, 0]]
        expected = 16
        self.assertEqual(solution.island_perimeter(data), expected)
        print('Success: test_island_perimeter')


def main():
    test = TestIslandPerimeter()
    test.test_island_perimeter()


if __name__ == '__main__':
    main()

Overwriting test_island_perimeter.py

In [3]:

%run -i test_island_perimeter.py

Success: test_island_perimeter