Katkat
Back

Count Interior Islands After Flooding

OracleData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of grid-based graph traversal and connected-component detection, focusing on flood-fill logic and the treatment of boundary-connected regions in a binary grid.

You are given an m x n binary grid representing land and water.

  • 1 = land
  • 0 = water

An island is a maximal group of land cells connected 4-directionally (up, down, left, right).

A closed island is an island that does not touch the boundary of the grid. Equivalently, you may imagine first flooding away every land cell that is connected to any boundary land cell, and then counting how many connected land components remain.

Write a function that returns the number of closed islands in the grid.

Clarifications:

  • Two land cells belong to the same island if they are connected horizontally or vertically.
  • Any island that touches the first/last row or first/last column should not be counted.
  • You may solve this using DFS, BFS, or Union-Find.