Largest Pond Size

You are given a two-dimensional matrix that represents a plot of land. Within the matrix there exist two values: ones which represent land and zeroes which represent water within a pond. Given that parts of a pond can be connected both horizontally and vertically (but not diagonally), return the largest pond size.

Note: You may assume that each zero within a given pond contributes a value of one to the total size of the pond.

Example(s)

Example 1:

Input: land = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]

Output: 1
Explanation:
There is one pond cell (0) at position (1,1).
Pond size = 1

Example 2:

Input: land = [
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1]
]

Output: 5
Explanation:
Connected pond cells (0s):
- Row 0: (0,1)
- Row 1: (1,0), (1,1), (1,2)
- Row 2: (2,1)
All connected horizontally and vertically.
Pond size = 5

Example 3:

Input: land = [
    [0, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 0, 0]
]

Output: 4
Explanation:
There are two ponds:
- Pond 1: (0,0), (0,1), (1,0) - size 3
- Pond 2: (1,2), (2,1), (2,2), (2,3) - size 4
Largest pond size = 4

Solution

The solution uses DFS/BFS to find connected components:

1. Traverse matrix: Visit each cell
2. Find ponds: When we find a 0 (water), explore all connected 0s
3. Count size: Count all cells in the connected component
4. Track maximum: Keep track of the largest pond size

JavaScript Solution

JavaScript Solution - DFS

/**
* Find largest pond size
* @param {number[][]} land - 2D matrix (1 = land, 0 = water)
* @return {number} - Size of largest pond
*/
function largestPondSize(land) {
if (!land || land.length === 0) return 0;

const rows = land.length;
const cols = land[0].length;
const visited = Array(rows).fill().map(() => Array(cols).fill(false));
let maxSize = 0;

/**
 * DFS to count pond size
 * @param {number} row - Current row
 * @param {number} col - Current column
 * @return {number} - Size of current pond
 */
function dfs(row, col) {
  if (
    row < 0 || row >= rows ||
    col < 0 || col >= cols ||
    visited[row][col] ||
    land[row][col] === 1  // Land, not water
  ) {
    return 0;
  }
  
  visited[row][col] = true;
  let size = 1; // Current cell contributes 1
  
  // Explore 4 directions (horizontally and vertically)
  size += dfs(row - 1, col); // up
  size += dfs(row + 1, col); // down
  size += dfs(row, col - 1); // left
  size += dfs(row, col + 1); // right
  
  return size;
}

// Traverse all cells
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    if (land[i][j] === 0 && !visited[i][j]) {
      // Found a new pond, explore it
      const pondSize = dfs(i, j);
      maxSize = Math.max(maxSize, pondSize);
    }
  }
}

return maxSize;
}

// Test cases
const land1 = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
];
console.log('Example 1:', largestPondSize(land1)); // 1

const land2 = [
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
];
console.log('Example 2:', largestPondSize(land2)); // 5

const land3 = [
[0, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 0, 0]
];
console.log('Example 3:', largestPondSize(land3)); // 4

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - DFS

from typing import List

def largest_pond_size(land: List[List[int]]) -> int:
  """
  Find largest pond size
  
  Args:
      land: 2D matrix (1 = land, 0 = water)
      
  Returns:
      int: Size of largest pond
  """
  if not land or not land[0]:
      return 0
  
  rows = len(land)
  cols = len(land[0])
  visited = [[False] * cols for _ in range(rows)]
  max_size = 0
  
  def dfs(row: int, col: int) -> int:
      """
      DFS to count pond size
      """
      if (
          row < 0 or row >= rows or
          col < 0 or col >= cols or
          visited[row][col] or
          land[row][col] == 1  # Land, not water
      ):
          return 0
      
      visited[row][col] = True
      size = 1  # Current cell contributes 1
      
      # Explore 4 directions (horizontally and vertically)
      size += dfs(row - 1, col)  # up
      size += dfs(row + 1, col)  # down
      size += dfs(row, col - 1)  # left
      size += dfs(row, col + 1)  # right
      
      return size
  
  # Traverse all cells
  for i in range(rows):
      for j in range(cols):
          if land[i][j] == 0 and not visited[i][j]:
              # Found a new pond, explore it
              pond_size = dfs(i, j)
              max_size = max(max_size, pond_size)
  
  return max_size

# Test cases
land1 = [
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]
print('Example 1:', largest_pond_size(land1))  # 1

land2 = [
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]
print('Example 2:', largest_pond_size(land2))  # 5

land3 = [
  [0, 0, 1, 0],
  [0, 1, 0, 1],
  [1, 0, 0, 0]
]
print('Example 3:', largest_pond_size(land3))  # 4

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (BFS)

Here's a BFS version:

JavaScript BFS

/**
 * BFS approach
 */
function largestPondSizeBFS(land) {
  if (!land || land.length === 0) return 0;
  
  const rows = land.length;
  const cols = land[0].length;
  const visited = Array(rows).fill().map(() => Array(cols).fill(false));
  let maxSize = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  
  function bfs(startRow, startCol) {
    const queue = [[startRow, startCol]];
    visited[startRow][startCol] = true;
    let size = 0;
    
    while (queue.length > 0) {
      const [row, col] = queue.shift();
      size++;
      
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        
        if (
          newRow >= 0 && newRow < rows &&
          newCol >= 0 && newCol < cols &&
          !visited[newRow][newCol] &&
          land[newRow][newCol] === 0
        ) {
          visited[newRow][newCol] = true;
          queue.push([newRow, newCol]);
        }
      }
    }
    
    return size;
  }
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (land[i][j] === 0 && !visited[i][j]) {
        const pondSize = bfs(i, j);
        maxSize = Math.max(maxSize, pondSize);
      }
    }
  }
  
  return maxSize;
}

Python BFS

from collections import deque

def largest_pond_size_bfs(land: List[List[int]]) -> int:
    """
    BFS approach
    """
    if not land or not land[0]:
        return 0
    
    rows = len(land)
    cols = len(land[0])
    visited = [[False] * cols for _ in range(rows)]
    max_size = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def bfs(start_row: int, start_col: int) -> int:
        queue = deque([(start_row, start_col)])
        visited[start_row][start_col] = True
        size = 0
        
        while queue:
            row, col = queue.popleft()
            size += 1
            
            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc
                
                if (
                    0 <= new_row < rows and
                    0 <= new_col < cols and
                    not visited[new_row][new_col] and
                    land[new_row][new_col] == 0
                ):
                    visited[new_row][new_col] = True
                    queue.append((new_row, new_col))
        
        return size
    
    for i in range(rows):
        for j in range(cols):
            if land[i][j] == 0 and not visited[i][j]:
                pond_size = bfs(i, j)
                max_size = max(max_size, pond_size)
    
    return max_size

Complexity

• Time Complexity: O(m × n) - Where m and n are the dimensions of the matrix. We visit each cell at most once.
• Space Complexity: O(m × n) - For the visited array. The recursion stack (DFS) or queue (BFS) also uses O(m × n) in the worst case.

Approach

The solution uses DFS/BFS to find connected components:

1. Traverse matrix:

   • Visit each cell in the matrix
   • When we find an unvisited 0 (water), it's a new pond

2. Explore pond:

   • Use DFS/BFS to explore all connected 0s
   • Connected means horizontally or vertically adjacent (not diagonal)
   • Mark all visited cells

3. Count size:

   • Count all cells in the connected component
   • Each 0 contributes 1 to the size

4. Track maximum:

   • Keep track of the largest pond size found
   • Return the maximum

Key Insights

• Connected components: Ponds are connected components of 0s
• 4-directional: Only check up, down, left, right (not diagonals)
• DFS/BFS: Both work to find connected components
• Visited array: Prevents revisiting cells
• Count all 0s: Each water cell contributes 1 to size

Step-by-Step Example

Let's trace through Example 1: land = [[1,1,1],[1,0,1],[1,1,1]]

Matrix:
  [1, 1, 1]
  [1, 0, 1]
  [1, 1, 1]

Traverse cells:
  (0,0): 1 (land) → skip
  (0,1): 1 (land) → skip
  (0,2): 1 (land) → skip
  (1,0): 1 (land) → skip
  (1,1): 0 (water) and not visited → new pond!
    dfs(1,1):
      Mark (1,1) as visited, size = 1
      Check neighbors:
        (0,1): 1 (land) → skip
        (2,1): 1 (land) → skip
        (1,0): 1 (land) → skip
        (1,2): 1 (land) → skip
      Return size = 1
    maxSize = max(0, 1) = 1
  (1,2): 1 (land) → skip
  (2,0): 1 (land) → skip
  (2,1): 1 (land) → skip
  (2,2): 1 (land) → skip

Result: maxSize = 1

Visual Representation

Example 1:
  [1, 1, 1]
  [1, 0, 1]  → Single pond cell, size = 1
  [1, 1, 1]

Example 2:
  [1, 0, 1]
  [0, 0, 0]  → All 0s connected, size = 5
  [1, 0, 1]
  
  Connected cells:
    (0,1) - (1,0) - (1,1) - (1,2) - (2,1)
    All connected horizontally/vertically

Example 3:
  [0, 0, 1, 0]
  [0, 1, 0, 1]  → Two ponds: size 3 and 4
  [1, 0, 0, 0]
  
  Pond 1: (0,0), (0,1), (1,0) - size 3
  Pond 2: (1,2), (2,1), (2,2), (2,3) - size 4
  Largest = 4

Edge Cases

• Empty matrix: Return 0
• All land: Return 0 (no ponds)
• All water: Return m × n (entire matrix is one pond)
• Single cell: Works correctly
• Multiple ponds: Returns size of largest

Important Notes

• 0 = water, 1 = land: Opposite of typical island problems
• 4-directional: Only horizontal/vertical connections (not diagonal)
• Connected components: All connected 0s form one pond
• Each 0 counts as 1: Size is number of water cells
• DFS/BFS: Both work for finding connected components

Related Problems

• Max Area of Island: Similar but for 1s instead of 0s
• Number of Islands: Count connected components
• Surrounded Regions: Different problem but uses similar DFS
• Walls and Gates: BFS problem

Takeaways

• Connected components can be found using DFS/BFS
• 4-directional means up, down, left, right (not diagonals)
• Visited array prevents revisiting cells
• Count all cells in the connected component
• O(m×n) time is optimal (must visit all cells)