Count islands in a binary grid

Q: Count islands in a binary grid

This question evaluates a candidate's ability to analyze grid-based data structures and identify connected components, testing spatial adjacency reasoning and state management within 2D arrays.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

You are given an m x n grid of characters where each cell is either '1' (land) or '0' (water). An island is formed by connecting adjacent land cells horizontally or vertically (not diagonally). The grid edges are surrounded by water.

Return the number of islands in the grid.

Input

grid : a 2D array/list of characters '0' and '1'

Output

An integer: the number of islands

Constraints

1 <= m, n <= 300
grid[i][j] ∈ {'0','1'}

Example

Input:

[
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

Output:

Explanation: There are three disconnected land components.