Katkat
Back

Count islands by requested sizes

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use graph traversal (DFS/BFS) to identify connected components in a grid and efficiently query their sizes using frequency maps.

Problem Description

Given a 2D binary grid consisting of 0s (water) and 1s (land), your task is to identify all islands and categorize them by their size. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

You need to implement a class IslandTracker that processes the grid and then answers queries for how many islands of a specific size exist.

Class Interface

class IslandTracker:
    def __init__(self, grid: List[List[int]]):
        # Initialize and pre-process the grid to find island sizes
        pass

    def count_islands_of_size(self, size: int) -> int:
        # Return the number of islands with exactly 'size' land cells
        pass

Constraints

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

Examples

Example 1: Input:

grid = [
  [1, 1, 0],
  [1, 0, 0],
  [0, 0, 1]
]

IslandTracker(grid) count_islands_of_size(3) returns 1 (the island at top-left has 3 cells). count_islands_of_size(1) returns 1 (the island at bottom-right has 1 cell).

Edge Cases

  • Empty grid or grid with no land.
  • A grid entirely filled with land (one large island).
  • Multiple islands of the same size.

Hints

Hint 1

Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the grid and find all connected components.

Hint 2

During traversal, keep a count of visited land cells to determine the total size of each island.

Hint 3

Store the size of each found island in a hash map (or frequency dictionary) where the key is the size and the value is the count of islands of that size.

Follow-up questions

  • How would your solution change if the grid were updated dynamically (e.g., a '1' becomes a '0') after initialization?
  • Can you solve this using the Disjoint Set Union (DSU) data structure instead of DFS/BFS?
  • What is the space complexity of your solution, and can it be optimized if you are allowed to modify the input grid?