Island Perimeter

Question

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

Explanation: The perimeter is the 16 yellow stripes in the image below:

Tags

• Array
• Hashmap

Thought

Two solutions:

• With hashmap
• Without hashmap

For the first algorithm, use the hashmap the count the number of lands with different number of neighboring lands.

For the second algorithm, the reference is http://bookshadow.com/weblog/2016/11/20/leetcode-island-perimeter/. We sum the perimeter of each single grid as individual then minus the total perimeter with 2 when found two lands are neighbors.

Code

with hashmap

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        neighborCount = collections.defaultdict(int)
        high = len(grid)
        width = len(grid[0])
        neighbor = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        for row in range(high):
            for col in xrange(width):
                if grid[row][col] == 0:
                    continue
                count = 0
                for x, y in neighbor:
                    newRow = row + x
                    newCol = col + y
                    if newRow < 0 or newRow >= high:
                        continue
                    if newCol < 0 or newCol >= width:
                        continue
                    if grid[newRow][newCol] == 1:
                        count += 1
                neighborCount[count] += 1
        ans = 0
        for i in xrange(5):
            ans += (4 - i) * neighborCount[i]
        return ans

without hashmap

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        h = len(grid)
        w = len(grid[0]) if h else 0
        ans = 0
        for x in range(h):
            for y in range(w):
                if grid[x][y] == 1:
                    ans += 4
                    if x > 0 and grid[x - 1][y]:
                        ans -= 2
                    if y > 0 and grid[x][y - 1]:
                        ans -= 2
        return ans