What is the time complexity of Number of Closed Islands?

The optimal solution has a time complexity of O(m*n).

What is the space complexity of Number of Closed Islands?

The space complexity is O(m*n).

What data structures are used to solve Number of Closed Islands?

This problem uses Array, Depth-First Search, Breadth-First Search, Union Find, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Number of Closed Islands?

Insight 1: Islands connected to the boundary of the grid cannot be closed islands, as they are not completely surrounded by water. Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to explore connected components (islands) in the grid.

Which companies ask LeetCode 1254. Number of Closed Islands in interviews?

This problem is frequently asked at DoorDash.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Number of Closed Islands - LeetCode 1254 Solution

Number of Closed Islands - Complete Solution Guide

Number of Closed Islands is LeetCode problem 1254, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0 s 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 = [

Detailed Explanation

The problem asks us to find the number of 'closed islands' in a given 2D grid. The grid contains 0s representing land and 1s representing water. An island is a group of connected 0s (land) that are 4-directionally adjacent (up, down, left, right). A 'closed island' is an island that is completely surrounded by 1s (water). This means no part of the island touches the boundary of the grid. The input is the 2D grid, and the output is the number of closed islands.

Solution Approach

The solution uses Depth-First Search (DFS) to solve this problem. First, it identifies and eliminates all islands connected to the boundaries of the grid, since these cannot be closed islands. It does this by traversing the boundaries and using DFS to mark all connected land cells as 'visited' (changing their value to 1, effectively turning them into water). Second, it iterates through the inner portion of the grid, searching for remaining land cells (0s). Each time it finds a land cell, it increments the count of closed islands and uses DFS to mark all connected land cells of that island as visited. This ensures that each closed island is counted only once.

Step-by-Step Algorithm

Step 1: Iterate through the borders of the grid (top, bottom, left, right).
Step 2: For each land cell (0) on the border, perform a DFS to change all connected land cells to water (1). This eliminates islands connected to the border.
Step 3: Iterate through the inner part of the grid (excluding the borders).
Step 4: If a land cell (0) is found, increment the closed island count and perform a DFS to change all connected land cells to water (1).
Step 5: Return the total count of closed islands.

Key Insights

Insight 1: Islands connected to the boundary of the grid cannot be closed islands, as they are not completely surrounded by water.
Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to explore connected components (islands) in the grid.
Insight 3: Modifying the grid in-place can be an efficient way to track visited cells during the search, avoiding the need for extra space for a 'visited' matrix.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Topics

This problem involves: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix.

Companies

Asked at: DoorDash.

Number of Closed Islands | LeetCode 1254

Medium

Array Depth-First Search Breadth-First Search Union Find Matrix

Time: O(m*n)Space: O(m*n)

Solution Code

Available in:

class Solution {
    public int closedIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // DFS function to mark connected land cells as visited (1).
        function (r, c) {
            if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == 1) {
                return;
            }

            grid[r][c] = 1;

            dfs(r + 1, c);
            dfs(r - 1, c);
            dfs(r, c + 1);
            dfs(r, c - 1);
        }

        // Step 1: Remove all land cells connected to the border.
        // These are islands that are not "closed".
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                dfs(i, 0);
            }
            if (grid[i][n - 1] == 0) {
                dfs(i, n - 1);
            }
        }

        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 0) {
                dfs(0, j);
            }
            if (grid[m - 1][j] == 0) {
                dfs(m - 1, j);
            }
        }

        // Step 2: Count the remaining islands.
        // Any '0' left must be part of a closed island.
        int closed_islands = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) {
                    closed_islands++;
                    dfs(i, j);
                }
            }
        }

        return closed_islands;
    }

    private void dfs(int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == 1) {
            return;
        }

        grid[r][c] = 1;

        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1254: Number of Closed Islands - Detailed explanation and solution approaches.

Topics

Array Depth-First Search Breadth-First Search Union Find Matrix

Companies

DoorDash

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1254

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Iterate through the borders of the grid (top, bottom, left, right).
2
Step 2: For each land cell (0) on the border, perform a DFS to change all connected land cells to water (1). This eliminates islands connected to the border.
3
Step 3: Iterate through the inner part of the grid (excluding the borders).
4
Step 4: If a land cell (0) is found, increment the closed island count and perform a DFS to change all connected land cells to water (1).
5
Step 5: Return the total count of closed islands.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(m*n)

📝

Why?

The time complexity is dominated by the iterations through the grid and the DFS calls. Each cell is visited a constant number of times, resulting in O(m*n). The space complexity is determined by the maximum depth of the recursion stack during the DFS, which can be proportional to the grid size in the worst-case.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Breadth-First Search (BFS)

Instead of using DFS, BFS can be used to explore the connected components (islands). A queue data structure would be used to manage the cells to be visited.

Time: O(m*n)Space: O(m*n)

Trade-offs: BFS and DFS have similar time complexities for this problem. BFS might use slightly more memory due to the queue, but it can be preferable if you need to control the order in which cells are visited, or if you want to avoid potential stack overflow issues with very large grids that could occur with a recursive DFS implementation.

Union Find

Union Find can be used to find connected components. Treat each cell as a node and connect adjacent land cells. Then, determine which connected components are closed by checking if any cell in that component touches the border.

Time: O(m*n * α(m*n)), where α is the inverse Ackermann function, which grows very slowly and can be considered almost constant for practical inputs.Space: O(m*n)

Trade-offs: Union Find is generally more complex to implement for this particular problem compared to DFS or BFS. The time complexity is also slightly worse because of the repeated union and find operations across the grid. Union Find is best suited if you need to efficiently perform multiple connectivity queries on the same grid or if the grid is very large and memory is a primary concern.

✨

Key Insights

1Insight 1: Islands connected to the boundary of the grid cannot be closed islands, as they are not completely surrounded by water.
2Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to explore connected components (islands) in the grid.
3Insight 3: Modifying the grid in-place can be an efficient way to track visited cells during the search, avoiding the need for extra space for a 'visited' matrix.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Empty grid or grid with zero rows or columns. The provided solutions implicitly handle this as the loops won't execute, and 0 will be returned.
Edge case 2: A grid completely filled with water (1s). The algorithm will correctly return 0 closed islands.
Edge case 3: A grid completely filled with land (0s). The algorithm will identify that the entire grid is one island connected to the border, so it returns 0.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to handle islands touching the boundaries. If the initial step of eliminating boundary islands is skipped, then the algorithm will incorrectly count open islands as closed islands.

✗Common mistake 2: Not marking visited cells during DFS or BFS. This can lead to infinite loops and incorrect results.

✗Common mistake 3: Incorrectly implementing DFS or BFS, such as missing boundary checks or incorrect neighbor traversal.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Image processing - Identifying enclosed regions in an image, such as detecting objects fully surrounded by a background.

🏦Real-world scenario 2: Network analysis - Determining isolated networks within a larger network.

🎮Real-world scenario 3: Flood fill algorithm - similar problems where connected regions needs to be filled or analyzed

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Number of Closed Islands"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?