Compute maximum perimeter among islands
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an `m x n` binary grid `grid` where:
- `grid[r][c] = 1` represents land
- `grid[r][c] = 0` represents water
An **island** is a maximal set of land cells connected **4-directionally** (up, down, left, right).
The **perimeter** of an island is the total number of unit edges of land cells that either:
- lie on the boundary of the grid, or
- border a water cell.
Return the **maximum perimeter** among all islands in the grid. If there is no land, return `0`.
## Input / Output
- **Input:** `grid: List[List[int]]`
- **Output:** `int` (maximum island perimeter)
## Constraints (typical interview constraints)
- `1 <= m, n <= 1000` (or similar)
- `grid[r][c]` is `0` or `1`
- Aim for `O(mn)` time
## Example
Given:
```
grid = [
[0,1,1,0],
[0,1,0,0],
[1,1,0,0]
]
```
There are two islands; return the larger island’s perimeter.
Quick Answer: This question evaluates a candidate's proficiency with grid traversal, connected-component identification, and perimeter computation in binary matrices, reflecting skills in array/graph processing and spatial reasoning.
Return the maximum perimeter among 4-connected land islands in a binary grid.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[0,1,1,0],[0,1,0,0],[1,1,0,0]],)
Expected Output: 12
Explanation: Compute perimeter of each island and take max.
Input: ([[0,0]],)
Expected Output: 0
Explanation: No land returns 0.
Input: ([[1]],)
Expected Output: 4
Explanation: Single land cell perimeter is 4.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.