prepbook
  • Introduction
  • Some common stuff
    • python __repr__
    • HackerRank input tips
  • Data Structures and Algorithms
    • Breadth first search
    • Depth First Search
    • Dijkstra
    • A* Search Algorithm
    • Binary Search
    • python counter
    • Sorting
      • Merge Sort
      • Quick Sort
    • Priority Queue
  • Multiprocessing vs Threading
  • Common Coding
    • Find loop in lin list
    • Maximum sum subarray
  • Coding
    • Valid palindrome
    • Palindrome number
    • Remove duplicates from sorted array
    • Island perimeter
    • Serialize and Deserialize Binary Tree
    • Valid Soduku
    • Word Pattern
    • Word Pattern II
    • Group Anagrams
    • Implement Trie
    • Deep copy list with random node
    • Palindrome Permutation
    • Combination Sum
    • Clone Graph
    • Generate parenthesis
    • Fibonacci Number
    • LRU Cache
    • Merge two sorted arrays in place
    • Hamming Distance
    • Merge K sorted arrays
    • Kth smalles element in BST
    • Kth largest element in an array
    • Remove duplicates from sorted list
    • Power of 2
    • Nested list weight sum
    • SIngle number in a list
    • Factor combinations
    • Delete node from BST
  • hacker Rank
    • Coding
      • print staircase
      • Drawing book
      • Challenge 0
      • Min-Max sum
  • WorkRelatedCoding
    • Rectangle Overlap
  • Python tips
Powered by GitBook
On this page

Was this helpful?

  1. Coding

Island perimeter

PreviousRemove duplicates from sorted arrayNextSerialize and Deserialize Binary Tree

Last updated 5 years ago

Was this helpful?

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:

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

        rows = len(grid)
        cols = len(grid[0])
        default_cell_peri = 4
        total_perimeter = 0
        #print 'rows=', rows, 'cols=', cols
        for r in xrange(rows):
            for c in xrange(cols):
                if grid[r][c] == 1:
                    cell_peri = default_cell_peri
                    #print 'r=', r, 'c=', c
                    # do inspection of e,w,n,s and decrement default_cell_peri
                    if r-1 >=0 and grid[r-1][c] == 1: # land in North
                        cell_peri -= 1
                    if r+1 <= (rows-1) and grid[r+1][c] == 1: # land in South
                        cell_peri -= 1
                    if c-1 >= 0 and grid[r][c-1] == 1: # land in West
                        cell_peri -= 1
                    if c+1 <= (cols-1) and grid[r][c+1] == 1: # land in East
                        cell_peri -= 1

                    total_perimeter += cell_peri

        return total_perimeter