Fill the Enclosed Ponds
Solve this ProblemYou are given a grid of water (1) and land (0). A pond is a group of water cells connected through shared sides. Every pond that does not touch the border of the grid is enclosed; fill all enclosed ponds with land and return the grid.
The key idea is to think from the outside in: water connected to the border can never be enclosed, so start from the border water and see what it reaches.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 12; grid[r][c] is 1 (water) or 0 (land) - ◆
A pond is a group of water cells connected through shared sides - ◆
A pond is enclosed when none of its cells lies on the border of the grid - ◆
Turn every enclosed pond into land (0) and return the grid; ponds that touch the border stay as they are
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Test Every Water Cell for a Route to the Border
BruteFor every water cell, run a separate search over the water around it and see whether it ever reaches a cell on the border. If it does, the cell keeps its water; if the search runs out first, the cell belongs to an enclosed pond and becomes land. Each of the R·C cells may search the whole grid: O((R·C)²).
O((R·C)²)O(R·C)1class Solution {
2 private boolean reachesBorder(int[][] grid, int sr, int sc) {
3 int rows = grid.length, cols = grid[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 boolean[][] seen = new boolean[rows][cols];
7 Deque<int[]> queue = new ArrayDeque<>();
8 seen[sr][sc] = true;
9 queue.add(new int[]{sr, sc});
10 while (!queue.isEmpty()) {
11 int[] cell = queue.poll();
12 if (cell[0] == 0 || cell[0] == rows - 1 || cell[1] == 0 || cell[1] == cols - 1) return true;
13 for (int d = 0; d < 4; d++) {
14 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
15 if (grid[nr][nc] == 1 && !seen[nr][nc]) {
16 seen[nr][nc] = true;
17 queue.add(new int[]{nr, nc});
18 }
19 }
20 }
21 return false;
22 }
23
24 public int[][] fillEnclosed(int[][] grid) {
25 int rows = grid.length, cols = grid[0].length;
26 int[][] result = new int[rows][cols];
27 for (int r = 0; r < rows; r++) result[r] = grid[r].clone();
28 for (int r = 0; r < rows; r++) {
29 for (int c = 0; c < cols; c++) {
30 if (grid[r][c] == 1 && !reachesBorder(grid, r, c)) {
31 result[r][c] = 0;
32 }
33 }
34 }
35 return result;
36 }
37}Optimal — Flood Inwards From the Border Water
OptimalTurn the question around. Start a single breadth-first search from all water cells on the border at once, and spread through connected water: every cell reached is "safe" because it is connected to the border. All other water cells are enclosed. Build the answer by keeping only the safe water. One search covers every cell once: O(R·C).
O(R·C)O(R·C)1class Solution {
2 public int[][] fillEnclosed(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 boolean[][] safe = new boolean[rows][cols];
7 Deque<int[]> queue = new ArrayDeque<>();
8 for (int r = 0; r < rows; r++) {
9 for (int c = 0; c < cols; c++) {
10 boolean onBorder = r == 0 || r == rows - 1 || c == 0 || c == cols - 1;
11 if (onBorder && grid[r][c] == 1) {
12 safe[r][c] = true;
13 queue.add(new int[]{r, c});
14 }
15 }
16 }
17 while (!queue.isEmpty()) {
18 int[] cell = queue.poll();
19 for (int d = 0; d < 4; d++) {
20 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
21 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !safe[nr][nc]) {
22 safe[nr][nc] = true;
23 queue.add(new int[]{nr, nc});
24 }
25 }
26 }
27 int[][] result = new int[rows][cols];
28 for (int r = 0; r < rows; r++) {
29 for (int c = 0; c < cols; c++) {
30 result[r][c] = safe[r][c] ? 1 : 0;
31 }
32 }
33 return result;
34 }
35}