How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bloomberg.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bloomberg during technical interviews.

Implement island counting with BFS and DFS

Quick Overview

A Bloomberg Software Engineer onsite coding question: count the number of islands (connected land regions) in an m x n grid under four-directional connectivity. It asks for a linear-time O(m·n) flood-fill plus a second, explicit breadth-first-search implementation, with correctness and complexity analysis, edge-case handling, tests, and a diagonal-adjacency follow-up.

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question You are given an `m x n` grid of characters where `'1'` represents land and `'0'` represents water. Count the number of distinct **islands** (connected land regions). Two land cells belong to the same island if they share a side — up, down, left, or right. Cells that touch only at a corner (diagonally) are **not** connected and count as separate islands. For example, the grid below contains **3** islands: ``` 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 ``` 1. **Primary solution.** Implement `countIslands(grid)` using any approach you like, running in `O(m·n)` time. Explain why it is correct and analyze its time and space complexity. 2. **Explicit BFS version.** Re-implement the count using an explicit breadth-first search (an iterative queue, no recursion). State its time and space complexity and compare the trade-offs against your first solution. 3. **Edge cases.** Make sure the solution behaves correctly on: an empty grid (`null` / `0` rows / `0` columns), an all-water grid, a single-cell grid, a grid that is entirely land, and very large grids. Confirm that diagonally-touching land cells are treated as separate islands. 4. **Testing.** Describe (or write) tests that validate the solution on several nontrivial cases, including the examples above. 5. **Follow-up.** Briefly describe how your solution would change if **diagonal (8-directional) adjacency** also counted as connected.

Quick Answer: A Bloomberg Software Engineer onsite coding question: count the number of islands (connected land regions) in an m x n grid under four-directional connectivity. It asks for a linear-time O(m·n) flood-fill plus a second, explicit breadth-first-search implementation, with correctness and complexity analysis, edge-case handling, tests, and a diagonal-adjacency follow-up.

Part 1: Count Islands in a Grid Using Any O(m*n) Approach

You are given an m x n grid where each cell is either '1' for land or '0' for water. Count how many distinct islands exist in the grid. An island is a maximal group of land cells connected horizontally or vertically. Diagonal contact does not connect islands. Your algorithm should run in O(m*n) time and should handle empty grids.

Constraints

grid may be None.
0 <= m <= 1000
0 <= n <= 1000
If m > 0 and n > 0, grid is rectangular.
Each cell is either '0' or '1'.
The intended time complexity is O(m*n).

Examples

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: The top-left block, the middle cell, and the bottom-right pair are three separate 4-directional islands.

Input: ([],)

Expected Output: 0

Explanation: An empty grid contains no land.

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

Expected Output: 5

Explanation: All five land cells touch only diagonally, so each is its own island.

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

Expected Output: 1

Explanation: All land cells are connected into one island.

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

Expected Output: 0

Explanation: An all-water grid has no islands.

Hints

Scan every cell. When you find unvisited land, you have discovered a new island.
After discovering an island, traverse from that cell to mark every land cell in the same connected component.

Part 2: Count Islands Using Explicit Iterative BFS

You are given an m x n grid where '1' represents land and '0' represents water. Count the number of distinct islands, where land cells are connected only by sharing an edge: up, down, left, or right. Implement the traversal using an explicit breadth-first search queue. Recursion is not allowed.

Constraints

grid may be None.
0 <= m <= 1000
0 <= n <= 1000
If m > 0 and n > 0, grid is rectangular.
Each cell is either '0' or '1'.
Use an iterative queue-based BFS, not recursion.

Examples

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: There are three 4-directionally connected land components.

Input: ([[]],)

Expected Output: 0

Explanation: A grid with zero columns contains no cells and therefore no islands.

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

Expected Output: 1

Explanation: A single land cell forms one island.

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

Expected Output: 2

Explanation: The two land cells touch diagonally only, so they are separate islands.

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

Expected Output: 5

Explanation: The grid contains five separate 4-directional connected components of land.

Hints

A queue processes cells layer by layer, but for counting islands, the important part is that it eventually visits the whole connected component.
Mark a land cell as visited when it is enqueued, not when it is dequeued, to avoid adding it multiple times.

Part 3: Count Islands with 8-Directional Diagonal Adjacency

You are given an m x n grid where '1' represents land and '0' represents water. Count the number of distinct islands when land cells are connected if they share either a side or a corner. In other words, use 8-directional adjacency: horizontal, vertical, and diagonal neighbors all count as connected.

Constraints

grid may be None.
0 <= m <= 1000
0 <= n <= 1000
If m > 0 and n > 0, grid is rectangular.
Each cell is either '0' or '1'.
The intended time complexity is O(m*n).

Examples

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

Expected Output: 1

Explanation: With diagonal adjacency, the top-left block connects diagonally to the middle cell, which connects diagonally to the bottom-right land.

Input: (None,)

Expected Output: 0

Explanation: A null grid contains no islands.

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

Expected Output: 1

Explanation: Every corner land cell is diagonally connected to the center land cell.

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

Expected Output: 0

Explanation: A single water cell does not form an island.

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

Expected Output: 2

Explanation: The first two land cells form one diagonal island, and the two rightmost land cells form another island.

Hints

The overall connected-component strategy is the same as 4-directional island counting.
The key change is the neighbor list: include all eight offsets around a cell.

Quick Overview