Count Islands with Diagonal Connectivity
Company: Google
Role: Frontend Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Count Islands with Diagonal Connectivity
Given a binary grid, count the connected components of cells containing 1. Two land cells are connected when their rows differ by at most one and their columns differ by at most one, so horizontal, vertical, and diagonal neighbors all connect.
### Function Signature
```text
count_islands_8(grid: list[list[int]]) -> int
```
### Valid Input Domain
The grid is rectangular, may be empty, and contains only zero and one.
### Exact Output Semantics
Return the number of eight-directionally connected land components. Empty grids and grids with no land return 0. Only the count is returned, so component order is irrelevant.
### Constraints
- 0 <= rows, columns <= 1,000.
- rows * columns <= 1,000,000.
### Public Examples
#### Example 1
Input: grid = [[1, 0], [0, 1]]
Output: 1
The two land cells touch diagonally and therefore form one island.
#### Example 2
Input: grid = [[1, 0, 0], [0, 0, 1], [1, 0, 0]]
Output: 3
None of the three land cells is within one row and one column of another.
### Hints
- A land cell has up to eight neighbors rather than four.
- Mark a cell when it enters the traversal frontier so it cannot be counted twice.
Overview: Practice counting binary-grid components when diagonal neighbors connect, changing the usual four-direction island definition.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
public:
int count_islands_8(vector>& grid)
{
int rows = grid.size();
if(rows == 0)
return 0;
int cols = grid[0].size();
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int islands = 0;
for(int r = 0; r < rows; r++)
{
for(int c = 0; c < cols; c++)
{
if(grid[r][c] == 0)
continue;
islands++;
queue> q;
q.push({r, c});
grid[r][c] = 0;
while(!q.empty())
{
auto [x, y] = q.front();
q.pop();
for(int d = 0; d < 8; d++)
{
int nx = x + dr[d];
int ny = y + dc[d];
if(nx < 0 || nx >= rows ||
ny < 0 || ny >= cols ||
grid[nx][ny] == 0)
continue;
grid[nx][ny] = 0;
q.push({nx, ny});
}
}
}
}
return islands;
}
};
Answer by mojahidislam221
class Solution {
public int count_islands_8(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
// All 8 possible directions
int[][] directions = {
{-1, -1}, {-1, 0}, {-1, 1},
{ 0, -1}, { 0, 1},
{ 1, -1}, { 1, 0}, { 1, 1}
};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// Found a new island
if (grid[r][c] == 1) {
islands++;
// DFS will visit the entire island
dfs(grid, r, c, directions);
}
}
}
return islands;
}
private void dfs(int[][] grid, int r, int c, int[][] directions) {
int rows = grid.length;
int cols = grid[0].length;
// Out of bounds or water
if (r < 0 || r >= rows ||
c < 0 || c >= cols ||
grid[r][c] == 0) {
return;
}
// Mark as visited
// This prevents visiting the same cell again.
grid[r][c] = 0;
// Explore all 8 neighboring cells
for (int[] direction : directions) {
int nr = r + direction[0];
int nc = c + direction[1];
dfs(grid, nr, nc, directions);
}
}
}