Problem 1: Island Counting
Approach Overview
To solve the island counting problem, we need to traverse a 2D grid where 1s represent land and 0s represent water. An island consists of all connected land cells horizontally or vertically. We'll explore two traversal strategies: Depth-First Search (DFS) and Breadth-First Search (BFS).
DFS Solution
The DFS approach involves scanning each cell in the grid. When encountering a land cell, we initiate a recursive exploration to mark all connected land cells as visited, counting each complete island as we finish its traversal.
public class IslandCounter {
/**
* Calculates the total number of islands in the grid
*
* @param map 2D grid representing the map
* @return Total count of islands
*/
public static int countIslands(int[][] map) {
int islandCount = 0;
int rows = map.length;
int cols = map[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (map[i][j] == 1) {
exploreIsland(map, i, j);
islandCount++;
}
}
}
return islandCount;
}
/**
* Recursive DFS to mark all connected land cells
*
* @param map The grid
* @param x Current row index
* @param y Current column index
*/
private static void exploreIsland(int[][] map, int x, int y) {
if (!isInBounds(map, x, y)) {
return;
}
if (map[x][y] != 1) {
return;
}
// Mark as visited
map[x][y] = 2;
// Explore all four directions
exploreIsland(map, x - 1, y);
exploreIsland(map, x + 1, y);
exploreIsland(map, x, y - 1);
exploreIsland(map, x, y + 1);
}
/**
* Checks if coordinates are within grid boundaries
*
* @param map The grid
* @param x Row index
* @param y Column index
* @return True if coordinates are valid
*/
private static boolean isInBounds(int[][] map, int x, int y) {
return x >= 0 && x < map.length && y >= 0 && y < map[0].length;
}
}
BFS Solution
The BFS approach uses a queue to systematically explore all connected land cells level by level. This method is particularly useful for larger grids where recursion depth might be a concern.
import java.util.LinkedList;
import java.util.Queue;
public class IslandBFSCounter {
/**
* Counts islands using BFS traversal
*
* @param map 2D grid representation
* @return Number of islands found
*/
public static int countWithBFS(int[][] map) {
if (map == null || map.length == 0) {
return 0;
}
int rows = map.length;
int cols = map[0].length;
boolean[][] visited = new boolean[rows][cols];
int islandCount = 0;
// Movement directions: down, right, up, left
int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
exploreWithBFS(map, visited, i, j, directions);
islandCount++;
}
}
}
return islandCount;
}
/**
* BFS exploration of connected land cells
*
* @param map The grid
* @param visited Visited status tracker
* @param startRow Starting row index
* @param startCol Starting column index
* @param dirs Movement directions
*/
private static void exploreWithBFS(int[][] map, boolean[][] visited,
int startRow, int startCol, int[][] dirs) {
Queue<int> queue = new LinkedList<>();
queue.add(new int[]{startRow, startCol});
visited[startRow][startCol] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0];
int col = current[1];
// Check all four directions
for (int[] dir : dirs) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (isValidCell(map, visited, newRow, newCol)) {
queue.add(new int[]{newRow, newCol});
visited[newRow][newCol] = true;
}
}
}
}
/**
* Validates if a cell is suitable for traversal
*
* @param map The grid
* @param visited Visited status tracker
* @param row Row index
* @param col Column index
* @return True if cell is valid land
*/
private static boolean isValidCell(int[][] map, boolean[][] visited,
int row, int col) {
return row >= 0 && row < map.length &&
col >= 0 && col < map[0].length &&
map[row][col] == 1 && !visited[row][col];
}
}
</int>
Problem 2: Maximum Island Area
Building on the island counting problem, this task requires finding the largest island by area. We'll apply similar tarversal techniques while tracking the size of each island encountered.
DFS Solution
public class MaxIslandFinder {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
/**
* Finds the maximum island area using DFS
*
* @param grid 2D grid representation
* @return Area of the largest island
*/
public static int findMaxArea(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int maxArea = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
int currentArea = calculateIslandArea(grid, visited, i, j);
maxArea = Math.max(maxArea, currentArea);
}
}
}
return maxArea;
}
/**
* Recursively calculates the area of an island
*
* @param grid The grid
* @param visited Visited status tracker
* @param row Current row index
* @param col Current column index
* @return Area of the island
*/
private static int calculateIslandArea(int[][] grid, boolean[][] visited,
int row, int col) {
if (!isInGrid(grid, row, col) || visited[row][col] || grid[row][col] != 1) {
return 0;
}
visited[row][col] = true;
int area = 1;
// Add areas from all four directions
for (int[] dir : DIRECTIONS) {
area += calculateIslandArea(grid, visited, row + dir[0], col + dir[1]);
}
return area;
}
/**
* Checks if coordinates are within grid boundaries
*
* @param grid The grid
* @param row Row index
* @param col Column index
* @return True if coordinates are valid
*/
private static boolean isInGrid(int[][] grid, int row, int col) {
return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length;
}
}
BFS Solution
import java.util.LinkedList;
import java.util.Queue;
public class MaxIslandBFSFinder {
/**
* Finds maximum island area using BFS
*
* @param grid 2D grid representation
* @return Area of the largest island
*/
public static int findMaxAreaWithBFS(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int maxArea = 0;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
Queue<int> queue = new LinkedList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
int currentArea = 0;
queue.add(new int[]{i, j});
grid[i][j] = 2; // Mark as visited
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0];
int col = cell[1];
currentArea++;
// Check all four directions
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (isLand(grid, newRow, newCol)) {
queue.add(new int[]{newRow, newCol});
grid[newRow][newCol] = 2; // Mark as visited
}
}
}
maxArea = Math.max(maxArea, currentArea);
}
}
}
return maxArea;
}
/**
* Checks if a cell is unvisited land
*
* @param grid The grid
* @param row Row index
* @param col Column index
* @return True if cell is valid land
*/
private static boolean isLand(int[][] grid, int row, int col) {
return row >= 0 && row < grid.length &&
col >= 0 && col < grid[0].length &&
grid[row][col] == 1;
}
}
</int>