LC#695. Max Area of Island

Posted on by user

Leetcode 695. Max Area of Island is an extension of the island problem where we need to find the largest island in a grid of 1s (land) and 0s (water).

Problem Statement

Given an m x n binary grid, find the maximum area of an island. An island is a group of 1s connected 4-directionally (up, down, left, right). You may assume all four edges of the grid are surrounded by 0.

Approach

We can solve this using DFS (Depth-First Search) or BFS (Breadth-First Search):

  1. Use DFS (or BFS) to explore the entire island when we find a 1.
  2. Mark visited cells as 0 to avoid counting them multiple times.
  3. Track the maximum size encountered.

Golang Solution (DFS)

package main

import (
	"fmt"
)

// Directions for 4-way connectivity
var directions = [][]int{
	{1, 0}, {-1, 0}, {0, 1}, {0, -1},
}

// DFS function to compute island size
func dfs(grid [][]int, r, c int) int {
	// Boundary conditions and if already visited or water
	if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) || grid[r][c] == 0 {
		return 0
	}

	// Mark cell as visited
	grid[r][c] = 0
	size := 1

	// Explore all 4 directions
	for _, dir := range directions {
		size += dfs(grid, r+dir[0], c+dir[1])
	}

	return size
}

// Function to find max area of an island
func maxAreaOfIsland(grid [][]int) int {
	maxSize := 0

	for r := 0; r < len(grid); r++ {
		for c := 0; c < len(grid[0]); c++ {
			if grid[r][c] == 1 {
				// Start DFS and update maxSize
				size := dfs(grid, r, c)
				if size > maxSize {
					maxSize = size
				}
			}
		}
	}

	return maxSize
}

// Main function to test
func main() {
	grid := [][]int{
		{0, 0, 1, 0, 0},
		{1, 1, 1, 0, 0},
		{0, 1, 0, 0, 1},
		{0, 0, 0, 1, 1},
	}

	fmt.Println("Max Area of Island:", maxAreaOfIsland(grid)) // Output: 5
}

Alternative Approach: BFS

Instead of DFS recursion, we can use BFS (queue-based traversal):

package main

import (
	"fmt"
	"container/list"
)

// BFS function to compute island size
func bfs(grid [][]int, r, c int) int {
	queue := list.New()
	queue.PushBack([]int{r, c})
	grid[r][c] = 0
	size := 0

	directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

	for queue.Len() > 0 {
		cell := queue.Remove(queue.Front()).([]int)
		x, y := cell[0], cell[1]
		size++

		for _, dir := range directions {
			nx, ny := x+dir[0], y+dir[1]
			if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[0]) && grid[nx][ny] == 1 {
				grid[nx][ny] = 0
				queue.PushBack([]int{nx, ny})
			}
		}
	}

	return size
}

// Function to find max area of an island
func maxAreaOfIslandBFS(grid [][]int) int {
	maxSize := 0

	for r := 0; r < len(grid); r++ {
		for c := 0; c < len(grid[0]); c++ {
			if grid[r][c] == 1 {
				// Start BFS and update maxSize
				size := bfs(grid, r, c)
				if size > maxSize {
					maxSize = size
				}
			}
		}
	}

	return maxSize
}

// Main function to test BFS
func main() {
	grid := [][]int{
		{0, 0, 1, 0, 0},
		{1, 1, 1, 0, 0},
		{0, 1, 0, 0, 1},
		{0, 0, 0, 1, 1},
	}

	fmt.Println("Max Area of Island (BFS):", maxAreaOfIslandBFS(grid)) // Output: 5
}

Complexity Analysis

Both DFS and BFS approaches have similar complexity:

  • Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.
  • Space Complexity:
    • DFS: O(m * n) in the worst case (recursion stack).
    • BFS: O(min(m, n)) for the queue.

Enhancements & Harder Versions

1️⃣ Include Diagonal Connectivity

Modify the directions array to include diagonal moves:

var directions = [][]int{
	{1, 0}, {-1, 0}, {0, 1}, {0, -1},
	{1, 1}, {1, -1}, {-1, 1}, {-1, -1}, // Diagonal moves
}

2️⃣ Find All Island Sizes (Instead of Just Max)

Modify the function to return all island sizes instead of just the max:

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

3️⃣ Ignore Islands Below a Size Threshold

Ignore islands smaller than k:

func maxAreaAboveThreshold(grid [][]int, k int) int {
	maxSize := 0
	for r := 0; r < len(grid); r++ {
		for c := 0; c < len(grid[0]); c++ {
			if grid[r][c] == 1 {
				size := dfs(grid, r, c)
				if size >= k && size > maxSize {
					maxSize = size
				}
			}
		}
	}
	return maxSize
}

Final Thoughts

  • DFS is easier to implement but can hit stack overflow for large grids.
  • BFS avoids recursion depth issues and is preferred for large-scale problems.
  • Enhancements like diagonal connections and minimum-size thresholds make the problem more complex.

🔥 This Golang solution is efficient, modular, and ready for harder variations of the island problem! 🚀

Leave a Reply