Katkat
Back

Count islands in a binary grid

SamsungSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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:

3

Explanation: There are three disconnected land components.