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.

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.

Hints

  1. 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).
  2. 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.
  3. 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.
  4. 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.

Loading coding console...