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 Technical Screen rounds at Snapchat.

What role is this question designed for?

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

Count islands with eight-direction adjacency

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given an m×n grid of characters '1' (land) and '0' (water). Count the number of islands, where cells are connected if they touch in any of the eight directions (N, NE, E, SE, S, SW, W, NW). Implement an algorithm that returns the island count. Discuss and implement one approach (BFS or DFS), analyze time and space complexity, and explain how you would handle very large grids to avoid recursion limits. Optional: outline a Union-Find solution and compare trade-offs.

Quick Answer: This question evaluates a candidate's competency in graph traversal algorithms and data-structure trade-offs by counting connected components on a grid with eight-direction adjacency, focusing on BFS/DFS behavior and optional Union-Find approaches.

You are given an m x n grid of characters where '1' represents land and '0' represents water. Count the number of islands. Unlike the classic version, two land cells belong to the same island if they touch in ANY of the eight directions: N, NE, E, SE, S, SW, W, NW (i.e. orthogonal AND diagonal neighbors are connected). Return the total number of islands. Implement an iterative flood fill (DFS with an explicit stack, or BFS) so the approach also works on very large grids without hitting the recursion limit. Example: Input: [['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']] Output: 1 Explanation: With 8-direction adjacency, the top-left 2x2 block touches the single land cell at (2,2) diagonally, which in turn touches the bottom-right pair diagonally, so every land cell forms one island.

Constraints

1 <= m, n <= 1000 (an empty grid returns 0)
grid[i][j] is either '1' (land) or '0' (water)
Cells are 8-directionally connected (orthogonal + diagonal)
Use an iterative flood fill to avoid recursion-depth limits on large grids

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: Diagonal links chain the 2x2 block to (2,2) and then to the bottom-right pair, so all land is one island.

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

Expected Output: 1

Explanation: The center cell is diagonally adjacent to all four corners, merging everything into a single island.

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

Expected Output: 1

Explanation: Top and bottom rows connect through the center cell via diagonal adjacency.

Input: [['0','0','0'],['0','0','0']]

Expected Output: 0

Explanation: No land cells, so there are zero islands.

Input: [['1']]

Expected Output: 1

Explanation: A single land cell is one island.

Input: []

Expected Output: 0

Explanation: An empty grid has no islands.

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

Expected Output: 4

Explanation: The four corner land cells are separated by water in all eight directions, giving four isolated islands.

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

Expected Output: 6

Explanation: The middle water row blocks diagonal links between rows, and gaps block links within each row, leaving six single-cell islands.

Hints

This is the classic 'Number of Islands' problem, but the neighbor set has 8 offsets instead of 4 — add the four diagonals (-1,-1), (-1,1), (1,-1), (1,1).
Scan every cell; when you find an unvisited '1', increment the count and flood-fill all reachable land from it, marking each visited so it is never counted again.
Use an explicit stack (or a queue for BFS) rather than recursion so a grid that is almost entirely land does not overflow the call stack.
For a Union-Find alternative, union each land cell with its land neighbors in only the SE, S, SW, and E directions (a forward-looking half of the 8) to avoid double work, then count distinct roots.

Quick Overview

This question evaluates a candidate's competency in graph traversal algorithms and data-structure trade-offs by counting connected components on a grid with eight-direction adjacency, focusing on BFS/DFS behavior and optional Union-Find approaches.