Coding questions · Samsung

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.

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.

Count Islands in a Binary Grid

Return the number of 4-directionally connected land components in a binary grid.