Quick Overview

This question evaluates understanding of graph and grid traversal concepts, specifically identifying connected components in a binary matrix and familiarity with traversal strategies such as BFS and DFS.

Solve Number of Islands

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question LeetCode 200. Number of Islands – Given a 2D grid of '1's (land) and '0's (water), count the number of islands. Follow-up: implement the solution with BFS and discuss corner-case handling. leetcode.com/problems/number-of-islands/description/

Quick Answer: This question evaluates understanding of graph and grid traversal concepts, specifically identifying connected components in a binary matrix and familiarity with traversal strategies such as BFS and DFS.

Given a 2D grid `grid` of '1's (land) and '0's (water), count the number of islands. An island is a group of land cells ('1') connected horizontally or vertically (not diagonally). You may assume all four edges of the grid are surrounded by water. Return the number of islands. This follow-up asks you to implement the traversal with **BFS**: for each unvisited land cell, start a breadth-first flood fill that marks every connected land cell as visited, then increment the island count once per BFS launch. **Example 1:** ``` Input: grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] Output: 1 ``` **Example 2:** ``` Input: grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] Output: 3 ``` **Corner cases to handle:** an empty grid (return 0), a grid with no land at all, a single-cell grid, and islands that touch the grid borders.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300 (an empty grid is also accepted and returns 0)
  • grid[i][j] is '0' or '1' (string characters, not integers)

Examples

Input: ([['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']],)

Expected Output: 1

Explanation: All the '1's form one connected blob, so there is exactly one island.

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)

Expected Output: 3

Explanation: Three separate clusters: the 2x2 block top-left, the lone '1' in the middle, and the two adjacent '1's bottom-right.

Hints

  1. Scan every cell. The first time you hit an unvisited '1', you've found a new island — increment the counter and launch a BFS from that cell.
  2. During BFS, mark each land cell as visited the moment you enqueue it (set it to '0' or use a visited set) so it is never counted or enqueued twice.
  3. Only move in the four cardinal directions (up/down/left/right). Diagonal neighbors do NOT connect islands.
  4. Guard the boundaries: before reading a neighbor, check 0 <= nr < rows and 0 <= nc < cols. Handle the empty-grid corner case up front by returning 0.

Loading coding console...