Katkat
Back

Count Islands in a Binary Grid

VisaSoftware Engineer I · Online Assessment
MediumSoftware Engineer IOnline AssessmentCoding & Algorithms

Last updated

This problem tests graph traversal techniques on a 2D grid, focusing on identifying connected components without modifying the original input or exceeding recursion limits.

Problem Statement

Given a 2D binary grid grid of size m x n where '1' represents land and '0' represents water, count the number of distinct islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Crucially, you must not mutate the input grid. You need to account for potential stack overflow issues if the grid contains long, snaking components.

Function Signature

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

Constraints

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

Examples

Example 1: Input:

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

Output: 2 Explanation: There are two islands. One is the 2x2 square of 1s, the other is the single 1 at [2][2].

Example 2: Input:

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

Output: 5 Explanation: Diagonals do not count as connections. Every '1' is isolated.

Edge Cases

  • Empty grid (return 0).
  • Grid with no land (return 0).
  • Grid completely filled with land (return 1).
  • Long, snake-like paths that could trigger recursion limits.

Hints

Hint 1

Since you cannot mutate the input, consider using a separate boolean matrix or a set to keep track of visited cells.

Hint 2

If the grid is very large and the land forms a long path, a recursive DFS might hit a stack limit; consider using an iterative approach with an explicit stack or a queue (BFS).

Hint 3

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

Follow-up questions

  • How would you optimize space complexity if the grid was massive and you were allowed to mutate it?
  • If the grid were so large that it did not fit into memory, how would you approach this problem using distributed processing?
  • How would the logic change if diagonal connections were also considered as part of an island?