Katkat
Back

Count Islands in a Grid

GeneralmotorsMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate a 2D grid and identify distinct connected components using graph traversal techniques like Depth-First Search (DFS) or Breadth-First Search (BFS).

Count Islands in a Grid

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of 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 all surrounded by water.

Function Signature

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

Constraints

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

Examples

Example 1: Input: grid = [["1","1","0"],["1","1","0"],["0","0","1"]] Output: 2 Explanation: The top-left cluster forms one island, and the bottom-right '1' forms another.

Example 2: Input: grid = [["1","1","1"],["0","1","0"],["1","1","1"]] Output: 1 Explanation: All land pieces are connected.

Edge Cases

  • Empty grid (return 0).
  • Grid with no land ('0's only).
  • Grid with all land ('1's only).

Hints

Hint 1

Iterate through every cell in the grid; when you encounter a '1', it marks the discovery of a new island.

Hint 2

Once land is found, use a traversal method like DFS or BFS to visit all connected land cells and mark them as visited (or change them to '0') to ensure each island is counted only once.

Hint 3

Consider modifying the grid in-place to track visited cells to save space, or use a separate boolean matrix if the input grid must remain immutable.

Follow-up questions

  • How would your approach change if diagonal connections were also considered as part of an island?
  • What is the time and space complexity of your solution in terms of m and n?
  • If the grid was extremely large and stored on disk, how would you approach counting islands without loading the entire grid into memory?