Largest Island Area in a Binary Grid Without Modifying the Input
Company: Flexport
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a rectangular grid in which every cell is either land (`1`) or water (`0`), return the area of the largest island. An island is a group of land cells connected horizontally or vertically, and its area is the number of cells it contains. The function must not modify the input grid: when it returns, `grid` must hold exactly the values the caller passed in.
### Function Signature
```python
def max_island_area(grid: list[list[int]]) -> int:
```
### Rules
- Two land cells belong to the same island when they share an edge (up, down, left or right). Cells that touch only at a corner are not connected.
- Everything outside the grid counts as water.
- Return the largest island area as a single integer, or `0` when the grid contains no land.
- `grid` must not be modified: no cell may be overwritten, and the caller may reuse the grid after the call.
### Constraints
- `1 <= m, n <= 50`, where `m = len(grid)` and `n = len(grid[0])`; every row has length `n`.
- Every cell is `0` or `1`.
- A single island may cover the whole grid, so its area can be as large as `m * n = 2500`.
### Examples
Cells are written as (row, column), counting from 0.
**Example 1**
```text
Input: grid = [[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]]
Output: 4
```
The 2 x 2 block in the top-left corner is one island of area 4. Cell (2, 2) touches that block only at a corner, so it is a separate island of area 1, and cells (3, 3) and (3, 4) form an island of area 2.
**Example 2**
```text
Input: grid = [[0, 0, 0],
[0, 0, 0]]
Output: 0
```
There is no land, so the answer is 0.
**Example 3**
```text
Input: grid = [[1, 0, 1, 1],
[1, 0, 0, 1],
[1, 1, 0, 1],
[0, 0, 0, 1]]
Output: 5
```
The left island consists of (0, 0), (1, 0), (2, 0) and (2, 1), area 4. The right island consists of (0, 2), (0, 3), (1, 3), (2, 3) and (3, 3), area 5. After the call, `grid` still holds exactly these values.
Overview: Given a grid of land and water cells, return the area of the largest island formed by horizontally or vertically connected land, without modifying the input grid. It tests connected-component traversal on a grid, visited-state bookkeeping when in-place marking is not allowed, and edge cases such as grids with no land.
Read the full Flexport Software Engineer interview experience this question came from
Given a rectangular `m x n` grid in which every cell is either land (`1`) or water (`0`), return the area of the largest island. An island is a group of land cells connected horizontally or vertically, and its area is the number of cells it contains.
Implement `max_island_area(grid)`.
### Rules
- Two land cells belong to the same island when they share an edge (up, down, left or right). Cells that touch only at a corner are not connected.
- Everything outside the grid counts as water.
- Return the largest island area as a single integer, or `0` when the grid contains no land.
- `grid` must not be modified: no cell may be overwritten, and when the function returns, `grid` must hold exactly the values the caller passed in, so the caller can reuse it.
### Constraints
- `1 <= m, n <= 50`, where `m = len(grid)` and `n = len(grid[0])`; every row has length `n`.
- Every cell is `0` or `1`.
- A single island may cover the whole grid, so the answer can be as large as `m * n = 2500`. No value ever exceeds 2^31 - 1, so a 32-bit `int` is sufficient in every language.
### Example 1
```text
Input: grid = [[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]]
Output: 4
```
Cells are written as (row, column), counting from 0. The 2 x 2 block in the top-left corner is one island of area 4. Cell (2, 2) touches that block only at a corner, so it is a separate island of area 1, and cells (3, 3) and (3, 4) form an island of area 2.
### Example 2
```text
Input: grid = [[1, 0, 1, 1],
[1, 0, 0, 1],
[1, 1, 0, 1],
[0, 0, 0, 1]]
Output: 5
```
The left island consists of (0, 0), (1, 0), (2, 0) and (2, 1), area 4. The right island consists of (0, 2), (0, 3), (1, 3), (2, 3) and (3, 3), area 5. After the call, `grid` still holds exactly these values.
Constraints
- 1 <= m, n <= 50, where m = len(grid) and n = len(grid[0]); every row has length n.
- Every cell is 0 or 1.
- A single island may cover the whole grid, so the answer can be as large as m * n = 2500; it never exceeds 2^31 - 1, so a 32-bit int suffices.
- grid must not be modified: when the function returns it must hold exactly the values the caller passed in.
Examples
Input: ([[0]],)
Expected Output: 0
Explanation: Smallest grid, one water cell: no land, so the answer is 0.
Input: ([[1]],)
Expected Output: 1
Explanation: Smallest grid, one land cell: a single island of area 1.
Hints
- An island is exactly the set of land cells you can reach from one another by stepping up, down, left or right through land; corner contact and anything past the border never join cells.
- Make sure every land cell is counted toward exactly one island, and only once.
- The grid has to come back unchanged, so any record of which cells you have already handled must live outside grid.