Katkat
Back

Count Closed Islands

OracleData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate a 2D grid using graph traversal algorithms like DFS or BFS while identifying connected components that do not touch the grid boundaries.

Problem Statement

Given a 2D grid consisting of 0s (land) and 1s (water), a closed island is a group of connected 0s that are fully surrounded by 1s. An island is considered 'closed' if it does not touch any of the four edges of the grid.

Write a function count_closed_islands(grid) that returns the total number of closed islands in the grid.

Input

  • grid: A list of lists of integers where grid[i][j] is either 0 or 1.

Constraints

  • 1 <= grid.length, grid[0].length <= 100

Examples

Example 1: Input:

[[1,1,1,1,1],
 [1,0,0,0,1],
 [1,0,1,0,1],
 [1,0,0,0,1],
 [1,1,1,1,1]]

Output: 1 Explanation: The central region of 0s is completely enclosed by 1s.

Example 2: Input:

[[0,0,1,0],
 [0,1,0,1],
 [0,1,1,1]]

Output: 0 Explanation: Any land connected to the boundary cannot be a closed island.

Function Signature

def count_closed_islands(grid: list[list[int]]) -> int:

Hints

Hint 1

Any land connected to the boundary of the grid cannot be part of a closed island.

Hint 2

Perform a traversal (DFS or BFS) starting from all land cells on the grid boundaries to mark them as 'not closed'.

Hint 3

After clearing boundary-connected land, count the remaining connected components of land in the interior of the grid.

Follow-up questions

  • How would you modify your solution if the island could also be connected diagonally?
  • What is the time and space complexity of your approach in terms of rows (R) and columns (C)?
  • How would you solve this problem if the grid was too large to fit entirely into memory and needed to be processed in chunks?