Grid-Based Island Problems
Counting Islands in a Grid
Given a 2D grid consisting of '1's (land) and '0's (water), we need to count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. We can assume all four edges of the grid are surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
Solution using Depth-First Search:
function countIslands(matrix) {
if (!matrix || matrix.length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
let islandCount = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (matrix[i][j] === '1') {
islandCount++;
exploreIsland(matrix, i, j);
}
}
}
return islandCount;
}
function exploreIsland(matrix, x, y) {
// Check boundaries and if current cell is water
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] === '0') {
return;
}
// Mark current cell as visited
matrix[x][y] = '0';
// Recursively visit all adjacent cells
exploreIsland(matrix, x + 1, y);
exploreIsland(matrix, x - 1, y);
exploreIsland(matrix, x, y + 1);
exploreIsland(matrix, x, y - 1);
}
Solution using Breadth-First Search:
function countIslands(matrix) {
if (!matrix || matrix.length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
let islandCount = 0;
const queue = [];
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (matrix[i][j] === '1') {
islandCount++;
matrix[i][j] = '0';
queue.push([i, j]);
while (queue.length > 0) {
const [x, y] = queue.shift();
// Check all four directions
if (x > 0 && matrix[x-1][j] === '1') {
queue.push([x-1, j]);
matrix[x-1][j] = '0';
}
if (x < rows-1 && matrix[x+1][j] === '1') {
queue.push([x+1, j]);
matrix[x+1][j] = '0';
}
if (y > 0 && matrix[x][y-1] === '1') {
queue.push([x, y-1]);
matrix[x][y-1] = '0';
}
if (y < cols-1 && matrix[x][y+1] === '1') {
queue.push([x, y+1]);
matrix[x][y+1] = '0';
}
}
}
}
}
return islandCount;
}
Finding the Farthest Ocean from Land
Given an N x N grid where each cell is marked as 0 (ocean) or 1 (land), we need to find the ocean cell that is farthest from any land cell. The distance is defined as the Manhattan distance: |x0 - x1| + |y0 - y1|.
If the grid contains only land or only ocean, we should return -1.
Example 1:
Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation:
The ocean cell at (1, 1) has the maximum distance of 2 from all land cells.
Example 2:
Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation:
The ocean cell at (2, 2) has the maximum distance of 4 from all land cells.
Solution using Multi-source BFS:
function findMaxDistance(grid) {
const size = grid.length;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
// Check if grid is all land or all ocean
let hasLand = false, hasOcean = false;
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
if (grid[i][j] === 1) hasLand = true;
if (grid[i][j] === 0) hasOcean = true;
}
}
if (!hasLand || !hasOcean) return -1;
// Initialize distance matrix and queue
const distance = new Array(size).fill().map(() => new Array(size).fill(-1));
const queue = [];
// Add all land cells to the queue
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
if (grid[i][j] === 1) {
queue.push([i, j]);
distance[i][j] = 0;
}
}
}
// Perform BFS
while (queue.length > 0) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const newX = x + dx;
const newY = y + dy;
if (newX >= 0 && newX < size && newY >= 0 && newY < size && distance[newX][newY] === -1) {
distance[newX][newY] = distance[x][y] + 1;
queue.push([newX, newY]);
}
}
}
// Find the maximum distance
let maxDist = 0;
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
if (grid[i][j] === 0) {
maxDist = Math.max(maxDist, distance[i][j]);
}
}
}
return maxDist;
}
Counting Closed Islands
Given a 2D grid where each cell is either land (0) or water (1), we need to count the number of closed islands. A closed island is an island completely surrounded by water, meaning all adjacent cells (up, down, left, right) of the island's perimeter are water.
Example 1:
Input: [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
The gray regions are closed islands as they are completely surrounded by water.
Example 2:
Input: [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
Solution using DFS:
function countClosedIslands(grid) {
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
function isClosed(x, y) {
// If we reach the boundary, this island is not closed
if (x < 0 || x >= rows || y < 0 || y >= cols) {
return false;
}
// If it's water, return true
if (grid[x][y] === 1) {
return true;
}
// Mark current cell as visited
grid[x][y] = 1;
// Check all four directions
const up = isClosed(x - 1, y);
const down = isClosed(x + 1, y);
const left = isClosed(x, y - 1);
const right = isClosed(x, y + 1);
// The island is closed only if all directions are closed
return up && down && left && right;
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === 0) {
if (isClosed(i, j)) {
count++;
}
}
}
}
return count;
}
Alternative Solution using BFS:
function countClosedIslands(grid) {
const rows = grid.length;
const cols = grid[0].length;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
let count = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === 0) {
let isClosed = true;
const queue = [[i, j]];
grid[i][j] = 1; // Mark as visited
while (queue.length > 0) {
const [x, y] = queue.shift();
// If we're at the boundary, this island is not closed
if (x === 0 || x === rows - 1 || y === 0 || y === cols - 1) {
isClosed = false;
}
// Check all four directions
for (const [dx, dy] of directions) {
const newX = x + dx;
const newY = y + dy;
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] === 0) {
queue.push([newX, newY]);
grid[newX][newY] = 1; // Mark as visited
}
}
}
if (isClosed) {
count++;
}
}
}
}
return count;
}
