Number of Closed Islands

Leetcode Daily Challenge (6th April, 2023)

6 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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.

Link: https://leetcode.com/problems/number-of-closed-islands/

Problem Explanation with examples:-

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

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

Intuition:-

For each cell in the grid, if it is 0 and not visited, then we check if it is closed using dfs.
Call dfs on the cell and if it returns True, then we increment count by 1.
In dfs, if the cell is out of bounds or visited, then we return True.
If the cell is 1, then we return True.
Else, we set isClosed to True and call dfs on the 4 adjacent cells.

Solution:-

Initialize m to the number of rows in the grid and n to the number of columns in the grid.
Initialize count to 0 and visited to a 2D array of size m * n with all elements set to False.
Define dfs as follows:
If the cell is out of bounds or visited, then we return True.
If the cell is 1, then we return True.
Else, we set isClosed to True and call dfs on the 4 adjacent cells.
Return isClosed at the end.
For each cell in the grid, if it is 0 and not visited, then we check if it is closed using dfs.
Call dfs on the cell and if it returns True, then we increment count by 1.
Return count at the end.

Code:-

JAVA Solution

public class Solution {
    public int closedIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        boolean[][] visited = new boolean[m][n];
        
        boolean dfs(int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n) {
                return false;
            }
            if (visited[i][j]) {
                return true;
            }
            visited[i][j] = true;
            if (grid[i][j] == 1) {
                return true;
            }
            boolean isClosed = true;
            isClosed &= dfs(i - 1, j);
            isClosed &= dfs(i + 1, j);
            isClosed &= dfs(i, j - 1);
            isClosed &= dfs(i, j + 1);
            return isClosed;
        }
        
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0 && !visited[i][j]) {
                    boolean isClosed = dfs(i, j);
                    if (isClosed) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

Python Solution

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        visited = [[False] * n for _ in range(m)]
        
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return False
            if visited[i][j]:
                return True
            visited[i][j] = True
            if grid[i][j] == 1:
                return True
            isClosed = True
            isClosed &= dfs(i - 1, j)
            isClosed &= dfs(i + 1, j)
            isClosed &= dfs(i, j - 1)
            isClosed &= dfs(i, j + 1)
            return isClosed
        
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if grid[i][j] == 0 and not visited[i][j]:
                    isClosed = dfs(i, j)
                    if isClosed:
                        count += 1
        return count

Complexity Analysis:-

TIME:-

The time complexity is O(m * n) where m is the number of rows in the grid and n is the number of columns in the grid. We visit each cell once.

SPACE:-

The space complexity is O(m * n) where m is the number of rows in the grid and n is the number of columns in the grid. We use a 2D array of size m n to store visited.

References:-

DFS