Largest island perimeter in a grid

You are given an m x n grid where each cell is either land ("1") or water ("0"). Land cells that touch horizontally or vertically (not diagonally) belong to the same island.

Treat every land cell as a unit square with four sides. A side is part of its island's perimeter when the cell on the other side is water or lies outside the grid. Water enclosed by an island counts as water, so its edges are part of the perimeter too.

Implement:

def max_island_perimeter(grid: list[list[str]]) -> int: ...

Return the largest perimeter of any island in the grid, or 0 if there is no land. The island with the most cells does not always have the largest perimeter.

Constraints

• 0 <= m, n <= 1000
• grid[i][j] is "0" or "1"
• Your solution should run in time linear in the number of cells and must not depend on deep recursion.

Example 1

grid = [
  ["1","1","0","0"],
  ["1","1","0","1"],
  ["0","0","0","1"],
  ["1","1","1","1"],
]

Output: 14. The top-left 2x2 block has perimeter 8. The six cells on the right and bottom form one L-shaped island with perimeter 14.

Example 2

grid = [
  ["1","1","1"],
  ["1","0","1"],
  ["1","1","1"],
]

Output: 16. The ring has 12 outer edges plus 4 edges facing the enclosed water.

Be ready to extend your solution, for example to land that is added one cell at a time.

Reconstructed from the reported question; details may differ from what interviewers ask.