1254. Number of Closed Islands

Number of Closed Islands (LeetCode 1254) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

How to solve Number of Closed Islands

Number of Closed Islands is a DFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Work towards the solution in these steps:

1. Exclude connected group of 0s on the corners because they are not closed island.
2. Return number of connected component of 0s on the grid.

The reference solution runs in O(m * n) time and O(1) space.

The Number of Closed Islands solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix.

Reported in interviews at Google, Amazon, Oracle, Uber.

How to practise Number of Closed Islands on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(1) space.

Open Number of Closed Islands in the code editor, or read the Number of Closed Islands editorial for a worked solution with its approach and complexity analysis.

Where Number of Closed Islands sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph DFS - Connected Components / Island Counting subpattern
• The full DSA patterns sheet

Problems related to Number of Closed Islands

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

• Count Sub Islands — Medium, same subpattern
• Detonate the Maximum Bombs — Medium, same subpattern
• Evaluate Division — Medium, same subpattern
• Flood Fill — Easy, same subpattern
• Island Perimeter — Easy, same subpattern
• Keys and Rooms — Medium, same subpattern

Number of Closed Islands FAQ