Google Interview Question — LeetCode 1254

In this post, we are going to discuss leetcode 1254 — Number of Closed Islands, which is asked in Google interviews.

Problem Analysis

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

My Thinking Process

This is a graph problem, where we need to count the number of connected 0s surrounded by 1 s.

We can start with the below steps:

1. DFS / BFS the four edges upon values of 0, and then overwrite the 0 to some other value to mark it as visited. These are the 0s which are not surrounded by 1s, which we will exclude.
2. Loop on the rest of the matrix, once we see an 0, we do DFS / BFS to mark all the connected 0s to some other values to mark them as visited.
3. Count the number of connected components.

Code Implementation

Base on the analysis above, below is my implementation of the problem.