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
Contents hide
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)
Recommended Posts
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022