Answer Exact Island-Size Existence Queries
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `island_size_queries(grid, queries)` for a rectangular binary grid. Cells containing `1` are land, cells containing `0` are water, and land cells connect only through shared edges.
For each integer in `queries`, return whether the grid contains at least one island with exactly that many cells. The grid does not change between queries, so preprocess it once and answer each query in `O(1)` average time.
For example, if the grid's island sizes are `2`, `2`, and `5`, queries `[1, 2, 5]` return `[false, true, true]`.
```hint Finish an island before recording its size
Run a complete depth-first or breadth-first traversal from each unvisited land cell, count all cells reached, and add the final count to a set.
```
```hint Separate preprocessing from the API
The expensive grid traversal happens once. Each later query should be only a hash-set membership check.
```
Quick Answer: Preprocess a binary grid so exact island-size queries can be answered in average O(1) time. Traverse each four-connected island once, store its completed size in a set, and keep query work independent of grid dimensions.
Implement island_size_queries(grid, queries) for a rectangular binary grid with four-directional land connectivity. Preprocess the unchanged grid once and return, for every query, whether at least one island has exactly that many cells.
Constraints
- 0 <= rows, columns <= 20, and every nonempty grid is rectangular.
- Every grid cell is 0 for water or 1 for land.
- 0 <= queries.length <= 20, and query values are integers from -400 through 400.
Examples
Input: ([[1, 1, 0, 1], [0, 0, 0, 1], [1, 1, 1, 0], [1, 1, 0, 0]], [1, 2, 5, 3])
Expected Output: [False, True, True, False]
Input: ([[1, 0, 1], [0, 1, 0], [1, 0, 1]], [1, 2, 5])
Expected Output: [True, False, False]
Hints
- Complete one breadth-first or depth-first traversal before recording that island's final size.
- Store the distinct completed sizes in a hash set so every query is a membership check.