1254. Number of Closed Islands

MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix
Leetcode Link

Problem Description

The problem presents a two-dimensional grid which consists of both land (0s) and water (1s). An island is defined as a group of land cells (or 0s) that are connected horizontally or vertically (4-directionally). A closed island is an island that is completely surrounded by water (1s), meaning it does not touch the edge of the grid at any point.

The goal is to count how many closed islands are present in the grid. For example, a 0 that is at the edge of the grid could be part of an island, but since it is touching the boundary, it cannot be considered a closed island.

Intuition

To solve this problem, we can perform a depth-first search (DFS) on each cell that is land (0). When we perform a DFS, we recursively visit each connected land cell and mark them as water (1) to avoid revisiting them. While performing the DFS, we also check if we ever touch the boundary of the grid (i.e., the row index i is 0 or m-1 or the column index j is 0 or n-1). If the DFS starts from a cell that never touches the boundary, it means we are on a closed island, and thus we should count it.

The function dfs(i, j) is designed to perform this task, where i and j are the row and column indices, respectively. This function marks the current cell as visited by setting grid[i][j] to 1. It then checks in all four directions and calls itself (the dfs function) on any connected land cell it finds. If any recursive call to dfs encounters the boundary, it propagates back a failure to recognize the island as closed by returning 0 (when bitwise & operator is applied). If an island is completely surrounded by water and doesn't touch the boundary at any point, dfs returns 1.

The pairwise(dirs) function combined with the surrounding for loop is a slight mistake in the code, possibly due to a misunderstanding of Python's itertools.pairwise, which doesnโ€™t apply here. Instead, it should loop over pairs of directions (like (dirs[k], dirs[k + 1]) for k in range 4) to check all four neighboring cells.

The final count of closed islands is obtained by initializing a sum with a generator expression that iterates over every cell in the grid and calls the dfs function if a land cell (0) is found. The result of dfs will only be 1 for cells that are part of a closed island, and thus the sum represents the total number of closed islands in the grid.

Note: The code provided seems to have a mistake with the pairwise(dirs) portion, which does not align with standard Python functions. The intention here might be to iterate over the directions in pairs to traverse up, right, down, and left in the grid.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution applies the depth-first search (DFS) algorithm to explore the grid and identify islands that are closed. Here's a step-by-step breakdown of the implementation:

  1. Initialization: A DFS function is defined, which will be used to explore the grid. Additionally, the size of the grid is noted in variables m (for rows) and n (for columns). The dirs array (which should contain pairs of directions to move up, right, down, and left) is used to facilitate the exploration of neighboring cells.

  2. Depth-First Search (DFS): The core of the solution is in the dfs function, which takes a cell (i, j) and:

    • Marks it as visited by setting grid[i][j] = 1.
    • Checks if the cell is within the boundary but not on it, meaning 0 < i < m - 1 and 0 < j < n - 1.
    • Iterates in all four directions based on the dirs array, and if an adjoining cell is unvisited land (grid[x][y] == 0), it recurs with these new coordinates.
    • If the recursive exploration touches the grid boundary, it will return 0, indicating this is not a closed island. If the exploration completes without touching the boundary, it returns 1, indicating a closed island.

  3. Counting Closed Islands: The main function now initializes a sum with a generator expression that loops over each cell in the grid. It calls dfs on cells that are land (0) and adds up the results. Each 1 returned by dfs denotes a closed island.

Here, it is worth noting that the "Reference Solution Approach" mentioned Union find. While the given solution does not utilize this pattern, it's relevant to acknowledge that Union find is another approach that can solve this problem. Union find, or disjoint-set data structure, would allow us to group land cells into disjoint sets and then count sets that do not touch the boundary of the grid, which effectively would identify closed islands. However, in the provided solution, DFS is used instead, which is an equally valid method for solving this problem.

The effectiveness of the DFS approach lies in its ability to mark and visit each cell only once, ensuring that the solution is efficient, with the time complexity being O(m*n), where m is the number of rows and n is the number of columns in the grid. The DFS algorithm is a natural fit for problems related to navigating and exploring grids, particularly in searching for connected components, such as islands in this context.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's take a small grid as an example to illustrate how the solution approach works. Consider the following grid:

11 1 1 1 0 1
21 0 0 1 0 1
31 1 1 1 1 1
41 1 1 0 0 1
51 0 0 1 1 1
61 1 1 1 1 1

In this grid, 1 represents water and 0 represents land. We want to find how many closed islands (areas of 0s that do not touch the grid's boundary) there are.

  1. We start by defining a dfs function and initializing the grid size, m and n, respectively. In this case, m = 6 (rows) and n = 6 (columns).

  2. We iterate over each cell in the grid. When we come across a land cell (0), we start the DFS process from it by calling our dfs function.

  3. We call the dfs function on the land cell in the second row, second column (grid[1][1]). The cell is marked as visited by setting it to 1. DFS checks the neighboring cells in four directions (up, down, left, right) based on a pair of directions.

  4. The DFS explores all connected land cells. For this example, it would change the following cells to 1:

11 1 1 1 0 1
21 1 1 1 0 1
31 1 1 1 1 1
41 1 1 0 0 1
51 0 0 1 1 1
61 1 1 1 1 1

  1. The DFS does not reach the boundary for this group of land cells, so it counts as one closed island.

  2. The next unvisited land cell initiates another DFS call which is on the fourth row, fourth column (grid[3][3]). The process is similar; it explores connected land cells:

11 1 1 1 0 1
21 1 1 1 0 1
31 1 1 1 1 1
41 1 1 1 1 1
51 0 0 1 1 1
61 1 1 1 1 1

  1. However, this time, the DFS touches the boundary at cell (grid[4][1]), so this island is not closed.

  2. The final unvisited land cell group starts at grid[4][1] and is similarly adjacent to the boundary.

At the end of this process, we see that only the first group of land cells (grid[1][1]) constitutes a closed island. Thus, the final count is 1.

The DFS algorithm efficiently identified areas that constitute closed islands, ensuring no cell is visited more than once, resulting in a time complexity of O(m*n). While the pairwise(dirs) part in the example content is confusing, the logic of the DFS here applies the correct four-directional checks by iterating over each direction pair to look at neighboring cells.

Solution Implementation

1class Solution:
2    def closedIsland(self, grid: List[List[int]]) -> int:
3        # Perform depth-first search to find and mark all cells connected to (i, j).
4        def dfs(row: int, col: int) -> int:
5            # Check if the cell is within the inner part of the grid
6            # Considering the edges can't form a closed island.
7            result = 1 if 0 < row < rows - 1 and 0 < col < cols - 1 else 0
8          
9            # Mark the current cell as visited
10            grid[row][col] = 1
11          
12            # Explore all four directions (up, right, down, left)
13            for direction in range(4):
14                new_row = row + directions[direction]
15                new_col = col + directions[direction + 1]
16              
17                # If the new cell is within the grid and not visited
18                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 0:
19                    # Continue the DFS and use logical AND to ensure all connected cells are closed
20                    result &= dfs(new_row, new_col)
21            return result
22
23        # Get the number of rows and columns in the grid
24        rows, cols = len(grid), len(grid[0])
25      
26        # Define the directions for the DFS. The pairs are (up, right, down, left).
27        directions = (-1, 0, 1, 0, -1)
28      
29        # Initialize the count of closed islands
30        closed_islands = 0
31      
32        # Iterate over each cell of the grid
33        for i in range(rows):
34            for j in range(cols):
35                # If the cell is land (0) and has not been visited
36                if grid[i][j] == 0:
37                    # Perform DFS from the current cell and check if it forms a closed island
38                    closed_islands += dfs(i, j)
39      
40        # Return the total count of closed islands
41        return closed_islands
42
1class Solution {
2    private int height;  // Variable to store the height of the grid
3    private int width;   // Variable to store the width of the grid
4    private int[][] grid; // 2D array to represent the grid itself
5
6    // Function to count the number of closed islands in the grid
7    public int closedIsland(int[][] grid) {
8        height = grid.length;    // Set the height of the grid
9        width = grid[0].length;  // Set the width of the grid
10        this.grid = grid;        // Assign the grid argument to the instance variable
11        int count = 0;           // Initialize count of closed islands
12      
13        // Iterate over each cell in the grid
14        for (int i = 0; i < height; ++i) {
15            for (int j = 0; j < width; ++j) {
16                // If the current cell is 0 (land), perform a DFS to mark the connected components
17                if (grid[i][j] == 0) {
18                    count += dfs(i, j); // Increment count if the land is part of a closed island
19                }
20            }
21        }
22        return count; // Return the total number of closed islands
23    }
24
25    // Helper method to perform DFS and determine if a connected component is a closed island
26    private int dfs(int row, int col) {
27        // If not on the border, assume it's a closed island; otherwise, it's not
28        int isClosed = (row > 0 && row < height - 1 && col > 0 && col < width - 1) ? 1 : 0;
29        grid[row][col] = 1; // Mark the current cell as visited by setting it to 1
30        int[] directions = {-1, 0, 1, 0, -1}; // Array to help traverse in 4 cardinal directions
31      
32        // Explore all 4 adjacent cells
33        for (int k = 0; k < 4; ++k) {
34            int nextRow = row + directions[k];           // Calculate the next row index
35            int nextCol = col + directions[k + 1];       // Calculate the next column index
36            // Verify if the adjacent cell is within the grid and if it is land (0)
37            if (nextRow >= 0 && nextRow < height && nextCol >= 0 && nextCol < width 
38                && grid[nextRow][nextCol] == 0) {
39                // Perform DFS on the adjacent cell and use logical AND to update the isClosed status
40                isClosed &= dfs(nextRow, nextCol); // If any part touches the border, it's not closed
41            }
42        }
43        return isClosed; // Return 1 if the island is closed, otherwise 0
44    }
45}
46
1class Solution {
2public:
3    int closedIsland(vector<vector<int>>& grid) {
4        // Get the number of rows and columns in the grid.
5        int rowCount = grid.size(), colCount = grid[0].size();
6      
7        // Initialize the count of closed islands to zero.
8        int closedIslandCount = 0;
9      
10        // Define directions for traversing the grid (up, right, down, left).
11        int directions[5] = {-1, 0, 1, 0, -1};
12
13        // Define a recursive Depth-First Search (DFS) lambda function to find closed islands.
14        function<int(int, int)> depthFirstSearch = [&](int row, int col) -> int {
15            // If the current cell is surrounded by non-border cells, mark as potential closed island.
16            int isClosedIsland = (row > 0 && row < rowCount - 1 && col > 0 && col < colCount - 1) ? 1 : 0;
17          
18            // Mark the current cell as visited.
19            grid[row][col] = 1;
20          
21            // Explore all 4 directions.
22            for (int k = 0; k < 4; ++k) {
23                int nextRow = row + directions[k], nextCol = col + directions[k + 1];
24                // If the next cell is on the grid and unvisited, continue the DFS.
25                if (nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount && grid[nextRow][nextCol] == 0) {
26                    // If any recursive DFS call returns 0, then it's not a closed island.
27                    isClosedIsland &= depthFirstSearch(nextRow, nextCol);
28                }
29            }
30            // Return whether the current cell is part of a closed island.
31            return isClosedIsland;
32        };
33
34        // Loop over all cells in the grid.
35        for (int i = 0; i < rowCount; ++i) {
36            for (int j = 0; j < colCount; ++j) {
37                // If the cell is land (0) and the DFS returns true for a closed island, increment the count.
38                closedIslandCount += (grid[i][j] == 0 && depthFirstSearch(i, j));
39            }
40        }
41
42        // Return the total count of closed islands found.
43        return closedIslandCount;
44    }
45};
46
1// Function to calculate the number of closed islands in a grid.
2// A closed island is a group of connected 0s that is completely surrounded by 1s (representing water),
3// and does not touch the edge of the grid.
4// @param grid - The 2D grid of 0s (land) and 1s (water).
5// @returns The count of closed islands.
6function closedIsland(grid: number[][]): number {
7    // Store the dimensions of the grid.
8    const rowCount = grid.length;
9    const colCount = grid[0].length;
10    // Directions for traversing up, down, left, and right in the grid.
11    const directions = [-1, 0, 1, 0, -1];
12    // DFS function to explore the cells in the grid.
13    const depthFirstSearch = (row: number, col: number): number => {
14        // A flag to indicate if the current island is closed.
15        // It's closed only if it doesn't touch the grid's edge.
16        let isClosed = row > 0 && col > 0 && row < rowCount - 1 && col < colCount - 1 ? 1 : 0;
17        // Mark the cell as visited by setting it to 1.
18        grid[row][col] = 1;
19        // Explore all 4 adjacent directions (up, down, left, right).
20        for (let k = 0; k < 4; ++k) {
21            const newRow = row + directions[k];
22            const newCol = col + directions[k + 1];
23            // Check if the new cell is within bounds and is land (0).
24            if (newRow >= 0 && newCol >= 0 && newRow < rowCount && newCol < colCount && grid[newRow][newCol] === 0) {
25                // If any recursive call returns 0, the island isn't closed.
26                isClosed &= depthFirstSearch(newRow, newCol);
27            }
28        }
29        // Return whether the island is closed.
30        return isClosed;
31    };
32  
33    // Initialize the count of closed islands.
34    let closedIslandsCount = 0;
35    // Iterate through all cells in the grid.
36    for (let row = 0; row < rowCount; ++row) {
37        for (let col = 0; col < colCount; col++) {
38            // If a cell is land and unvisited, perform DFS.
39            if (grid[row][col] === 0) {
40                closedIslandsCount += depthFirstSearch(row, col);
41            }
42        }
43    }
44    // Return the final count of closed islands.
45    return closedIslandsCount;
46}
47
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Time and Space Complexity

The given Python code is a solution for finding the number of "closed islands" in a 2D grid, where 0 represents land and 1 represents water. A "closed island" is one that is surrounded by water and doesn't touch the edge of the grid. The algorithm uses Depth-First Search (DFS) to explore the grid.

Time Complexity

The time complexity of the code is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because the algorithm potentially visits each cell in the grid once. The DFS is started only if the current cell is a 0 (land), and then it marks every visited land cell as 1 (water) to prevent revisiting. In the worst case, all cells in the grid will be traversed once.

Space Complexity

The space complexity of the DFS is O(m * n) in the worst case. This might happen when the depth of the recursion stack grows proportionally to the number of cells in the worst-case scenario, such as when the grid forms a large area of contiguous land. The space is used by the recursion call stack during the depth-first search.

However, if we consider that modern Python implementations use a technique called "tail-recursion elimination" in some cases, the space complexity can be effectively less than O(m * n) for some grids because not all calls will result in an additional stack frame. But in the analysis of DFS, it is conventional to consider the worst-case scenario regarding recursion.

The additional space used by the dirs variable and a few integer variables is negligible compared to the recursive stack space, thus not affecting the overall space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ