Number of Closed Islands - Practice Coding Problems

Number of Closed Islands - Problem

Given a 2D grid consisting of 0s (land) and 1s (water), an island is a maximal 4-directionally connected group of 0s.

A closed island is an island that is totally surrounded by 1s on all sides (left, top, right, bottom).

Return the number of closed islands.

Input & Output

Example 1 — Basic Closed Island

$ 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

💡 Note: There are two closed islands: one 2x2 island in the middle-left area, and one single cell island. The rightmost land cells touch the boundary so they don't count.

Example 2 — No Closed Islands

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

› Output: 0

💡 Note: All land cells are connected to the boundary (top, bottom, left, or right edges), so there are no closed islands.

Example 3 — Single Closed Island

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

› Output: 1

💡 Note: The center island is completely surrounded by water (1s). The single land cell in the middle is also connected to the outer ring, forming one large closed island.

Constraints

1 ≤ grid.length, grid[i].length ≤ 100
grid[i][j] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with 0s (land) and 1s (water)

Identify Islands

Find connected groups of land cells (0s)

Check Boundaries

Determine which islands touch grid edges

Count Closed

Count islands that don't touch boundaries

Key Takeaway

🎯 Key Insight: A closed island is completely surrounded by water and doesn't touch any grid boundary

Asked in

a Amazon 15 M Microsoft 12 G Google 8 f Facebook 6

The key insight is that a closed island cannot touch the grid boundary. Best approach is Two-Pass DFS: first mark all boundary-connected land, then count remaining island groups. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(m×n)	O(m×n)	For each unvisited land cell, use DFS to check if the entire island is closed
Two-Pass DFS	O(m×n)	O(m×n)	First pass marks all boundary-connected land, second pass counts remaining islands

Brute Force DFS — Algorithm Steps

Iterate through each cell in the grid
For each unvisited land cell, start DFS
During DFS, mark cells as visited and check if any cell touches boundary
If entire island doesn't touch boundary, increment count

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Land

Scan grid for unvisited land cells (0)

DFS Explore

Use DFS to visit all connected land cells

Check Boundary

Track if any cell touches grid boundary

Count Closed

Increment count if island doesn't touch boundary

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool dfs(int** grid, bool** visited, int i, int j, int m, int n) {
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] == 1) {
        return true;
    }
    
    visited[i][j] = true;
    
    bool isClosed = true;
    if (i == 0 || i == m-1 || j == 0 || j == n-1) {
        isClosed = false;
    }
    
    isClosed &= dfs(grid, visited, i+1, j, m, n);
    isClosed &= dfs(grid, visited, i-1, j, m, n);
    isClosed &= dfs(grid, visited, i, j+1, m, n);
    isClosed &= dfs(grid, visited, i, j-1, m, n);
    
    return isClosed;
}

int solution(int** grid, int m, int n) {
    bool** visited = (bool**)malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        visited[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0 && !visited[i][j]) {
                if (dfs(grid, visited, i, j, m, n)) {
                    count++;
                }
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        free(visited[i]);
    }
    free(visited);
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for [[1,1,1],[0,0,1],[1,1,1]] format
    int m = 0, n = 0;
    // Count rows
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && i > 0 && line[i-1] != '[') m++;
    }
    
    // Allocate grid
    int** grid = (int**)malloc(m * sizeof(int*));
    
    // Parse the grid
    char* ptr = line + 1; // Skip first '['
    for (int i = 0; i < m; i++) {
        ptr++; // Skip '['
        
        // Count columns for first row
        if (i == 0) {
            char* temp = ptr;
            while (*temp != ']') {
                if (*temp == ',' || (*temp >= '0' && *temp <= '9')) {
                    if (*temp != ',') n++;
                }
                temp++;
            }
        }
        
        grid[i] = (int*)malloc(n * sizeof(int));
        
        for (int j = 0; j < n; j++) {
            grid[i][j] = *ptr - '0';
            ptr++;
            if (j < n-1) ptr++; // Skip comma
        }
        ptr += 2; // Skip '],'
    }
    
    int result = solution(grid, m, n);
    printf("%d\n", result);
    
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Visit each cell at most once during DFS traversal

✓ Linear Growth

Space Complexity

O(m×n)

Recursion depth can go up to m×n in worst case (entire grid is one island)

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler