Katkat
Back

Count Islands in a Binary Grid

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform graph traversal on a 2D grid while adhering to strict memory constraints and preserving the integrity of the original data structure.

Problem Statement

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), write a function to return the total number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

You must not modify the input grid. Because the grid can be very large, you should avoid deep recursion to prevent stack overflow errors.

Function Signature

def count_islands(grid: List[List[int]]) -> int:

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • The input grid must remain unchanged after the function completes.

Examples

Example 1: Input: grid = [[1, 1, 0], [1, 0, 0], [0, 0, 1]] Output: 2 Explanation: There is an island at the top-left corner and a single cell island at the bottom-right.

Example 2: Input: grid = [[1, 1, 1], [0, 0, 0], [1, 1, 1]] Output: 2

Edge Cases

  • Empty grid or grids with no land ('1').
  • A grid completely filled with land.
  • Grids with a single row or single column.

Hints

Hint 1

Since you cannot modify the input grid, consider using a secondary data structure like a 2D boolean array or a set to keep track of visited cells.

Hint 2

To avoid stack overflow, use an iterative approach with a queue (Breadth-First Search) or a stack (Depth-First Search) instead of recursion.

Hint 3

Iterate through every cell in the grid; whenever you encounter an unvisited '1', increment your island count and trigger a traversal to mark all connected land cells as visited.

Follow-up questions

  • How would you modify your solution if the grid was too large to fit entirely in memory?
  • What is the space complexity of your solution, and can you optimize it if you were allowed to mutate the grid?
  • How would the logic change if the diagonal connections were also considered part of an island?