Island Perimeter | LeetCode | Solution Explained

463. Island Perimeter is an easy problem on LeetCode. I explore the Iterative solution and the depth first search (dfs) solution. Problem link

Iterative Solution

  • Each land cell adds 4 to the perimeter
  • We remove 1 from its preimeter when the cell in neighbourhood is
    • existing
    • and is also a land cell
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        
        for x in range(m):
            for y in range(n):
                if not grid[x][y]: continue # if 0, skip
# now we are looking at a land cell
                ans += 4 
# the below removes 1 for every land cell in neighbourhood
                if x > 0 and grid[x-1][y]: ans -= 1
                if x < m-1 and grid[x+1][y]: ans -= 1
                if y > 0 and grid[x][y-1]: ans -= 1
                if y < n-1 and grid[x][y+1]: ans -= 1
                    
        return ans

DFS Solution

  • mostly the same logic
  • change: instead of checking the status of neighbours (out of bounds or water), we go to the neighbour
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(x, y):
            if not (0 <= x <= m-1 and 0 <= y <= n-1): return 1
            if grid[x][y] == 0: return 1
            if grid[x][y] == -1: return 0
            grid[x][y] = -1
            
            count = 0
            count += dfs(x+1, y)
            count += dfs(x-1, y)
            count += dfs(x, y+1)
            count += dfs(x, y-1)
        
            return count
        
        for x in range(m):
            for y in range(n):
                if grid[x][y]: 
                    return dfs(x, y)

    Leave a Reply

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