[Daily Leetcode] 463. Island Perimeter

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:

Solution

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        sides = 0
        for i in range(len(grid)):
            prev = 0
            for t in grid[i]:
                if t!=prev:
                    prev = t
                    sides+=1
            if grid[i][len(grid[i])-1]==1:
                sides+=1
       
        for i in range(len(grid[0])):
            prev = 0
            for t in range(len(grid)):
                if grid[t][i]!=prev:
                    prev = grid[t][i]
                    sides+=1
            if grid[len(grid)-1][i]==1:
                sides+=1
       
        return sides

Analysis

This algorithm in this solution is very simple, it calculates the number of difference between the previous block and the next block, both is row and in column. The output is the total number of differences.

Any simpler way?

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        def equal(x,y):
            if x != y:
                return 1
            else:
                return 0
        dif = 0
        for i in grid + map(list, zip(*grid)):
            dif += sum(map(equal, [0] + i, i + [0]))
        return dif

The algorithm behind these two codes are the same, but this one looks much simpler as it has harnessed some function integrated in python:
1. map(list, zip(*grid)) means to convert columns and rows in grid. It has appended another transposed grid to the initial one
2. map(equal, [0] + i, i + [0]) aims at compare the corresponding integer in list [0 , i] and [i, 0], i corresponds each row in the matrix, which is a simpler way to compare this block with the previous block.
([0] + [1,2,3,4,5,6,7,8] = [0,1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8] + [0] = [1,2,3,4,5,6,7,8,0])

4 thoughts on “[Daily Leetcode] 463. Island Perimeter

  1. Hello!
    Thank you for your explanation, I can see what your explanation.But I am puzzled with the whole idea of the algorithms,e.g what does sides mean ? we want to determine the perimeter of the island, in my view ,sides is the numbers of islands. I do not the relationship between sides and perimeter. Trouble you help me explain my problem. Thank you very much again.

  2. Hello!
    I have completely understood the algorithm with you help. I want to learn a lot later from you. In addition , can you help me explain question 496 in algorithm of leetcode ,it is Input: nums1 = [4,1,2], nums2 = [1,3,4,2] , Output: [-1,3,-1]
    class Solution(object):
    def nextGreaterElement(self, findNums, nums):
    d = {}
    st = []
    ans = []

    for x in nums:
    while len(st) and st[-1] < x :
    d[st.pop()] = x
    st.append(x)
    for x in findNums:
    ans.append(d.get(x,-1))
    return ans

    I want to know about the whole idea of algorithm, the same as you previous explanation. thank you.

Leave a Reply

Your email address will not be published. Required fields are marked *