Quick Overview

Count four-directionally connected islands in a potentially large binary grid without changing the caller's input. The problem emphasizes complete graph traversal, empty and narrow grids, and avoiding recursive stack overflow on long components.

Count Islands in a Binary Grid

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Given a rectangular grid of land and water, count the connected islands. Land cells connect only through shared horizontal or vertical edges. ## Function Contract Implement `count_islands(grid)`, where `grid` is a list of equal-length strings containing `"0"` and `"1"`. Return an integer. ## Rules - `"1"` is land and `"0"` is water. - Diagonal contact does not connect two land cells. - The input may be empty. - The function may mutate a local copy, but callers must not observe a changed input. ## Constraints - `0 <= len(grid) <= 2000`. - When non-empty, `1 <= len(grid[0]) <= 2000`. - The grid contains at most `2,000,000` cells. ## Examples ```text grid = [ "11000", "11010", "00100", "00011" ] output = 4 ```

Quick Answer: Count four-directionally connected islands in a potentially large binary grid without changing the caller's input. The problem emphasizes complete graph traversal, empty and narrow grids, and avoiding recursive stack overflow on long components.

Given a rectangular grid represented as equal-length strings of 0 and 1, return the number of connected islands. A 1 is land and a 0 is water. Land cells connect only through shared horizontal or vertical edges, never diagonally. The grid may be empty. The caller must not observe any mutation of the input.

Constraints

  • 0 <= len(grid) <= 2000.
  • When nonempty, all rows have equal length and 1 <= len(grid[0]) <= 2000.
  • The grid contains at most 2000000 cells, each equal to 0 or 1.
  • Only horizontal and vertical edges connect land cells.

Examples

Input: (['11000', '11010', '00100', '00011'],)

Expected Output: 4

Explanation: Four separate four-neighbor components are present.

Input: ([],)

Expected Output: 0

Explanation: An empty grid contains no islands.

Hints

  1. Starting a traversal from each unseen land cell counts one new connected component.
  2. Mark a neighbor when adding it to the worklist so it is not added twice.

Loading coding console...