< Back




463. Island Perimeter

Fun problem, we've got a 2D matrix with just one island. Its perimeter is defined by the number of
edges of the island that touch the water, including the edges on the boundaries of the matrix. We can
solve this by visiting each cell and counting the number of edges that aren't land. We baseline
assume that for a given piece of land the number of edges touching the water is 4. We look in all
directions, up, right, left, and down - if they're valid directions for the matrix and contain land
we subtract by 1. We then add the number of edges for this piece of land to our answer.

The solution is as follows:


  class Solution:
      def islandPerimeter(self, grid: List[List[int]]) -> int:
          n, m, ans = len(grid), len(grid[0]), 0
          directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

          def is_valid(q: int, p: int) -> bool:
              return -1 < q < n and -1 < p < m

          for i in range(n):
              for j in range(m):
                  if grid[i][j]:
                      this_ans = 4

                      for dy, dx in directions:
                          ny, nx = i + dy, j + dx

                          if is_valid(ny, nx):
                              if grid[ny][nx]:
                                  this_ans -= 1

                      ans += this_ans

          return ans


_ Time Complexity:

  O(n * m) - Where n is the number of rows and m is the number of columns. We visit each cell in the
  matrix. 

_ Space Complexity:

  O(1) - We maintain a constant amount of space for the directions list and the variables n, m, ans.