Count the Stranded Land Tiles
Solve this ProblemYou are given a grid of land (1) and sea (0). From a land tile you may walk to a neighbouring land tile (up, down, left or right), and from a land tile on the border of the grid you may walk off the grid. Count the land tiles from which it is impossible to leave the grid.
Instead of testing every tile, start from the border: everything connected to border land can leave the grid, and whatever is left over is stranded.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 12; grid[r][c] is 1 (land) or 0 (sea) - ◆
A move goes from a land tile to a neighbouring land tile (up, down, left, right), or off the grid from a land tile on the border - ◆
A land tile is stranded when NO sequence of such moves can leave the grid - ◆
Return the number of stranded land tiles
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Search From Every Land Tile Towards the Border
BruteFor every land tile, run its own search over connected land and check whether that search ever touches a border tile. When it does not, the tile is stranded and is counted. Each tile may explore the whole grid, so the total is 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 countStranded(int[][] grid) {
25 int rows = grid.length, cols = grid[0].length;
26 int count = 0;
27 for (int r = 0; r < rows; r++) {
28 for (int c = 0; c < cols; c++) {
29 if (grid[r][c] == 1 && !reachesBorder(grid, r, c)) {
30 count++;
31 }
32 }
33 }
34 return count;
35 }
36}Optimal — One Search Started From All Border Land
OptimalStart a breadth-first search from every land tile on the border simultaneously and spread through connected land: everything reached can walk off the grid. Then count the land tiles that were never reached. One search plus one counting pass: O(R·C).
O(R·C)O(R·C)1class Solution {
2 public int countStranded(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 count = 0;
28 for (int r = 0; r < rows; r++) {
29 for (int c = 0; c < cols; c++) {
30 if (grid[r][c] == 1 && !safe[r][c]) count++;
31 }
32 }
33 return count;
34 }
35}