Katkat
Back

Count closed islands in a grid

OracleData Scientist · Technical Screen
EasyData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate a 2D grid using graph traversal algorithms like DFS or BFS while handling specific boundary constraints to identify closed regions.

Problem Statement

You are given a 2D grid of size m x n consisting of 0s (land) and 1s (water). A closed island is a group of 0s surrounded by 1s on all four sides (horizontal and vertical). Specifically, a group of 0s is considered a closed island if it is completely enclosed by 1s and does not touch the boundary of the grid.

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

Constraints

  • 1 <= m, n <= 100
  • grid[i][j] is either 0 or 1.

Examples

Example 1:

Input: grid = [
  [1, 1, 1, 1],
  [1, 0, 0, 1],
  [1, 1, 1, 1]
]
Output: 1
# Explanation: The '0's in the middle are surrounded by '1's.

Example 2:

Input: grid = [
  [0, 0, 1],
  [0, 1, 0],
  [1, 1, 1]
]
Output: 0
# Explanation: The '0's at the boundary cannot form a closed island.

Function Signature

def countClosedIslands(grid: list[list[int]]) -> int:
    pass

Hints

Hint 1

Any island that touches the boundary of the grid cannot be a closed island.

Hint 2

Perform a traversal (DFS or BFS) to 'sink' or mark all land cells connected to the boundary as visited, effectively ignoring them.

Hint 3

After clearing boundary-connected land, perform a second pass to count the remaining isolated groups of '0's.

Follow-up questions

  • How would your solution change if diagonal connections were also considered part of an island?
  • What is the time and space complexity of your solution in terms of grid dimensions M and N?
  • Can you solve this using a Disjoint Set Union (DSU) data structure instead of DFS/BFS?