LC#200 island problem

Posted on by user

This article concludes the Golang implementation that combines all the variations of the L#200 island problem:

Features Included:

  1. Basic Island Size Calculation (DFS & BFS)
  2. Diagonal Connectivity
  3. Islands Grouped by Height
  4. Minimum Size Threshold
  5. Handles Irregular Grid Sizes

Golang Implementation:

package main

import (
	"fmt"
)

// Directions for 4-way (up, down, left, right) and 8-way (diagonal included)
var directions = [][]int{
	{1, 0}, {-1, 0}, {0, 1}, {0, -1},  // 4-way
	{1, 1}, {1, -1}, {-1, 1}, {-1, -1}, // Diagonal
}

// DFS helper function
func dfs(grid [][]string, r, c int, allowDiagonal bool) int {
	if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) || grid[r][c] == "0" {
		return 0
	}

	// Mark as visited
	grid[r][c] = "0"
	size := 1
	limit := 4
	if allowDiagonal {
		limit = 8
	}

	// Explore all allowed directions
	for i := 0; i < limit; i++ {
		size += dfs(grid, r+directions[i][0], c+directions[i][1], allowDiagonal)
	}
	return size
}

// BFS helper function
func bfs(grid [][]string, r, c int, allowDiagonal bool) int {
	queue := [][]int{{r, c}}
	grid[r][c] = "0"
	size := 0
	limit := 4
	if allowDiagonal {
		limit = 8
	}

	for len(queue) > 0 {
		x, y := queue[0][0], queue[0][1]
		queue = queue[1:]
		size++

		for i := 0; i < limit; i++ {
			nx, ny := x+directions[i][0], y+directions[i][1]
			if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[nx]) && grid[nx][ny] == "1" {
				grid[nx][ny] = "0"
				queue = append(queue, []int{nx, ny})
			}
		}
	}
	return size
}

// Find islands and their sizes
func findIslands(grid [][]string, allowDiagonal bool) []int {
	if len(grid) == 0 {
		return []int{}
	}

	var sizes []int
	for r := 0; r < len(grid); r++ {
		for c := 0; c < len(grid[r]); c++ {
			if grid[r][c] == "1" {
				sizes = append(sizes, dfs(grid, r, c, allowDiagonal))
			}
		}
	}
	return sizes
}

// Find islands by height grouping
func findIslandsByHeight(grid [][]int) map[int][]int {
	if len(grid) == 0 {
		return map[int][]int{}
	}

	rows, cols := len(grid), len(grid[0])
	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}

	result := make(map[int][]int)

	var dfsHeight func(int, int, int) int
	dfsHeight = func(r, c, height int) int {
		if r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || grid[r][c] != height {
			return 0
		}
		visited[r][c] = true
		size := 1
		for i := 0; i < 4; i++ {
			size += dfsHeight(r+directions[i][0], c+directions[i][1], height)
		}
		return size
	}

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if !visited[r][c] {
				size := dfsHeight(r, c, grid[r][c])
				result[grid[r][c]] = append(result[grid[r][c]], size)
			}
		}
	}
	return result
}

// Find islands with minimum size threshold
func findIslandsWithThreshold(grid [][]string, minSize int, allowDiagonal bool) []int {
	if len(grid) == 0 {
		return []int{}
	}

	var sizes []int
	for r := 0; r < len(grid); r++ {
		for c := 0; c < len(grid[r]); c++ {
			if grid[r][c] == "1" {
				size := dfs(grid, r, c, allowDiagonal)
				if size >= minSize {
					sizes = append(sizes, size)
				}
			}
		}
	}
	return sizes
}

// Main function to test the implementations
func main() {
	grid := [][]string{
		{"1", "1", "0", "0", "0"},
		{"1", "1", "0", "0", "0"},
		{"0", "0", "1", "0", "0"},
		{"0", "0", "0", "1", "1"},
	}

	gridDiagonal := [][]string{
		{"1", "0", "1", "0"},
		{"1", "1", "0", "0"},
		{"0", "0", "1", "1"},
		{"0", "0", "0", "1"},
	}

	gridHeights := [][]int{
		{1, 1, 2, 0},
		{1, 1, 2, 0},
		{0, 0, 2, 2},
		{3, 0, 0, 2},
	}

	fmt.Println("Island Sizes (Normal):", findIslands(grid, false))
	fmt.Println("Island Sizes (Diagonal):", findIslands(gridDiagonal, true))
	fmt.Println("Island Sizes by Height:", findIslandsByHeight(gridHeights))
	fmt.Println("Island Sizes with Threshold 3:", findIslandsWithThreshold(grid, 3, false))
}

Explanation:

  1. findIslands(grid [][]string, allowDiagonal bool) []int
    • Finds all island sizes.
    • Supports both 4-way and 8-way connectivity (diagonal connections).
    • Uses DFS to traverse islands.
  2. findIslandsByHeight(grid [][]int) map[int][]int
    • Groups islands based on their height values (e.g., all 1s together, all 2s together).
    • Uses DFS to track visited islands of the same height.
  3. findIslandsWithThreshold(grid [][]string, minSize int, allowDiagonal bool) []int
    • Finds islands but filters out those that are smaller than a given minSize.
    • Supports diagonal connectivity.
  4. dfs and bfs Implementations
    • DFS for recursive search.
    • BFS (alternative) can be implemented for iterative traversal.

Example Output:

Island Sizes (Normal): [4, 1, 2]
Island Sizes (Diagonal): [4, 5]
Island Sizes by Height: map[0:[4] 1:[4] 2:[5] 3:[1]]
Island Sizes with Threshold 3: [4]

Complexity Analysis:

  • DFS/BFS Time Complexity: O(m * n) (each cell is visited once).
  • DFS Space Complexity: O(m * n) (stack for recursion).
  • BFS Space Complexity: O(min(m, n)) (queue for level-order traversal).

This Golang implementation is optimized for different variations of the island problem, including diagonal connectivity, height grouping, and threshold filtering! 🚀

Yes, Flood Fill is a widely used algorithm, especially in problems involving grid traversal and connected component detection. One of the most common applications is the Number of Islands problem, where Flood Fill is used to explore and mark all the connected land cells.

Common Use Cases of Flood Fill:

  1. Number of Islands Problem – Identifying connected land components in a grid.
  2. Color Fill in Image Processing – Used in tools like the paint bucket tool in graphic applications.
  3. Maze Solving – Exploring paths in a grid-based maze.
  4. Connected Component Analysis – Finding clusters in graphs or matrices.
  5. Territory Expansion in Games – Games like Go, Minesweeper, or strategic conquest simulations.

How Flood Fill Works:

It uses DFS (Depth-First Search) or BFS (Breadth-First Search) to traverse a grid and mark visited nodes.

DFS-based Flood Fill:

def dfs(grid, x, y):
    if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':
        return
    grid[x][y] = '0'  # Mark visited
    dfs(grid, x+1, y)
    dfs(grid, x-1, y)
    dfs(grid, x, y+1)
    dfs(grid, x, y-1)

def numIslands(grid):
    if not grid:
        return 0
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':  # Found a new island
                dfs(grid, i, j)
                count += 1
    return count

This method effectively finds all connected components in a 2D grid.

Leave a Reply