Katkat
Back

Find Maximum Island Perimeter

SnapchatSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests grid traversal techniques (DFS/BFS) and the ability to calculate boundary contributions within a connected component in a 2D matrix.

Problem Statement

You are given an m x n binary matrix grid where 1 represents land and 0 represents water. An island is a group of 1s connected 4-directionally (horizontally or vertically).

Given the coordinates of a specific land cell (r, c) that is part of an island, calculate the total perimeter of the island to which that cell belongs. The perimeter is defined as the total length of the edges of the island that are adjacent to water or the boundary of the grid.

Function Signature

def islandPerimeter(grid: List[List[int]], r: int, c: int) -> int:

Examples

Example 1: Input:

grid = [
 [0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]
],
r = 2, c = 1

Output: 16 Explanation: The cell (2, 1) belongs to the large island consisting of all land cells. The total perimeter of this connected component is 16.

Constraints

  • m == grid.length, n == grid[0].length
  • 1 <= m, n <= 100
  • grid[r][c] is guaranteed to be 1.
  • The island does not contain lakes (internal holes).

Edge Cases

  • The island consists of only one cell (perimeter should be 4).
  • The island is located entirely along the grid boundaries.

Hints

Hint 1

First, use a graph traversal algorithm like BFS or DFS to identify all cells belonging to the same connected component as (r, c).

Hint 2

Keep track of visited cells to ensure you don't count the same cell twice during your traversal.

Hint 3

For every land cell in the component, its contribution to the perimeter is 4 minus the number of its 4-directional neighbors that are also land.

Follow-up questions

  • How would you modify your solution if the island could contain internal lakes that should not be counted as part of the perimeter?
  • What is the time and space complexity of your solution in terms of grid dimensions M and N?
  • Can you solve this without using extra space for a 'visited' set by modifying the input grid temporarily?