# Posts tagged as “island”

Given a 2D grid consists of 0s (land) and 1s (water).  An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1


Example 3:

Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2


Constraints:

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

## Solution: DFS/Backtracking

For each connected component, if it can reach the boundary then it’s not a closed island.

Time complexity: O(n*m)
Space complexity: O(n*m)

# Problem

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5


Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3


Example 3:

Input: stones = [[0,0]]
Output: 0


Note:

1. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

# Solution 2: Union Find

Find all connected components (islands)

Ans = # of stones – # of islands

# Related Problems

Problem:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Example 2:

# Idea: DFS

Use DFS to find a connected component (an island) and mark all the nodes to 0.

Time complexity: O(mn)

Space complexity: O(mn)

# Related Problems

Mission News Theme by Compete Themes.