What is the time complexity of Count Sub Islands?

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

What is the space complexity of Count Sub Islands?

The space complexity is O(m*n).

What data structures are used to solve Count Sub 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 Count Sub Islands?

Insight 1: Islands in `grid2` that have a corresponding land cell in `grid1` as water are *not* sub-islands. We can effectively eliminate these islands by 'sinking' them in `grid2`. Insight 2: After sinking the non-sub-island components, we simply count the remaining islands in `grid2`. Each remaining island is guaranteed to be a sub-island.

Which companies ask LeetCode 1905. Count Sub Islands in interviews?

This problem is frequently asked at DoorDash, X, Zepto.

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

Count Sub Islands - LeetCode 1905 Solution

Count Sub Islands - Complete Solution Guide

Count Sub Islands is LeetCode problem 1905, 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

You are given two m x n binary matrices grid1 and grid2 containing only 0 's (representing water) and 1 's (representing land). An island is a group of 1 's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells. An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2 . Return the number of islands in grid2 that are considered sub-islands . Example 1: Input: gr

Detailed Explanation

The problem asks us to find the number of "sub-islands" present in `grid2`. A sub-island is an island in `grid2` that is also entirely contained within an island in `grid1`. Both grids contain only 0s (water) and 1s (land), and an island is a group of 1s connected horizontally or vertically (4-directionally). The goal is to count how many islands in `grid2` are sub-islands of islands in `grid1`.

Solution Approach

The solution first eliminates all islands in `grid2` that have at least one cell that corresponds to a water cell in `grid1`. Then, it counts the remaining islands in `grid2`. Each remaining island is guaranteed to be a sub-island since we've removed any island in `grid2` that isn't fully contained within an island in `grid1`. We use a `sink` function (implemented using a stack-based DFS) to set all cells of an island to 0. The `sink` function is called when an island in `grid2` has a corresponding 0 in `grid1`. Finally, we iterate through the modified `grid2` and count the remaining islands, sinking them as we go to avoid overcounting.

Step-by-Step Algorithm

Step 1: Iterate through each cell in `grid2`.
Step 2: If a cell in `grid2` is land (1) AND the corresponding cell in `grid1` is water (0), then call the `sink` function to eliminate the entire island connected to that cell in `grid2`.
Step 3: After eliminating the non-sub-islands in `grid2`, iterate through `grid2` again.
Step 4: If a cell in the modified `grid2` is land (1), then it represents a sub-island. Increment the sub-island count and call `sink` to eliminate this island to avoid counting it again.
Step 5: Return the final sub-island count.

Key Insights

Insight 1: Islands in `grid2` that have a corresponding land cell in `grid1` as water are *not* sub-islands. We can effectively eliminate these islands by 'sinking' them in `grid2`.
Insight 2: After sinking the non-sub-island components, we simply count the remaining islands in `grid2`. Each remaining island is guaranteed to be a sub-island.
Insight 3: Depth-First Search (DFS) or Breadth-First Search (BFS) is an efficient way to identify and sink connected components (islands) in the grids.

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, X, Zepto.

Count Sub Islands | LeetCode 1905

Medium

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

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

Solution Code

Available in:

import java.util.Stack;

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m = grid1.length;
        int n = grid1[0].length;

        
        
        
        
        
        

        

        
        Action sink = (r, c) -> {
            Stack<int[]> stack = new Stack<>();
            stack.push(new int[]{r, c});
            grid2[r][c] = 0;

            while (!stack.isEmpty()) {
                int[] curr = stack.pop();
                int row = curr[0];
                int col = curr[1];

                int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                for (int[] dir : directions) {
                    int nr = row + dir[0];
                    int nc = col + dir[1];

                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid2[nr][nc] == 1) {
                        grid2[nr][nc] = 0;
                        stack.push(new int[]{nr, nc});
                    }
                }
            }
        };

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid2[r][c] == 1 && grid1[r][c] == 0) {
                    sink.apply(r, c);
                }
            }
        }

        int sub_island_count = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid2[r][c] == 1) {
                    sub_island_count++;
                    sink.apply(r, c);
                }
            }
        }

        return sub_island_count;
    }

    interface Action {
        void apply(int r, int c);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1905: Count Sub Islands - Detailed explanation and solution approaches.

Topics

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

Companies

DoorDashXZepto

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:1905

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 each cell in `grid2`.
2
Step 2: If a cell in `grid2` is land (1) AND the corresponding cell in `grid1` is water (0), then call the `sink` function to eliminate the entire island connected to that cell in `grid2`.
3
Step 3: After eliminating the non-sub-islands in `grid2`, iterate through `grid2` again.
4
Step 4: If a cell in the modified `grid2` is land (1), then it represents a sub-island. Increment the sub-island count and call `sink` to eliminate this island to avoid counting it again.
5
Step 5: Return the final sub-island count.

💡

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 nested loops iterate through all m*n cells of the grid. The `sink` function, in the worst case, might be called for every cell. Each call explores an island, and because each cell in `grid2` is visited at most a constant number of times (once during the initial iteration, and potentially once during a `sink` call), the overall complexity remains O(m*n). The stack/recursion depth within the sink function can also grow up to m*n 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

Union Find

An alternative approach is to use the Union Find data structure. We can build a Union Find structure for both `grid1` and `grid2`. Then, for each island in `grid2`, we check if all its cells are part of the same connected component in `grid1`. If so, it is a sub-island.

Time: O(m*n * alpha(m*n)), where alpha is the inverse Ackermann function, which grows very slowly and can be considered almost constant.Space: O(m*n) to store the parent arrays for Union Find.

Trade-offs: Union Find might be slightly more complex to implement than DFS, but it can be more efficient if we need to perform many connectivity queries on the grids. However, given the constraints on grid size, the DFS approach is generally preferred due to its simpler implementation.

✨

Key Insights

1Insight 1: Islands in `grid2` that have a corresponding land cell in `grid1` as water are *not* sub-islands. We can effectively eliminate these islands by 'sinking' them in `grid2`.
2Insight 2: After sinking the non-sub-island components, we simply count the remaining islands in `grid2`. Each remaining island is guaranteed to be a sub-island.
3Insight 3: Depth-First Search (DFS) or Breadth-First Search (BFS) is an efficient way to identify and sink connected components (islands) in the grids.

📚

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 grids. The code handles this correctly as the loops will not execute, and 0 will be returned.
Edge case 2: `grid2` contains no islands. The code correctly returns 0 as the `sub_island_count` remains 0.
Edge case 3: `grid1` contains all water, and `grid2` contains islands. The code will eliminate all islands in `grid2`, correctly returning 0.
Edge case 4: `grid1` and `grid2` are identical and contain an island. The code will correctly identify and count that island as a sub-island.
Edge case 5: `grid2` has an island, but `grid1` only contains a portion of it. The code correctly identifies that this island is NOT a sub-island because a portion of grid2's island will overlap with grid1's water, and the initial sinking process will correctly eliminate those parts of the island.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to modify `grid2` after identifying a cell in `grid2` that corresponds to water in `grid1`. Without modifying `grid2`, the algorithm will incorrectly count non-sub-islands.

✗Common mistake 2: Overcounting islands because the `sink` function is not called after counting a sub-island. This results in the same island being counted multiple times.

✗Common mistake 3: Not handling the edge cases where either `grid1` or `grid2` (or both) are empty or contain only water. Proper initialization and conditional checks are crucial.

✗Common mistake 4: Incorrectly implementing the DFS/BFS for sinking islands, leading to incorrect island identification and counting.

✅

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 where we want to identify objects that are contained within other objects. For example, detecting logos within a larger image.

🏦Real-world scenario 2: Network analysis where we want to find sub-networks that are contained within larger networks. This could be useful for identifying specific groups of users within a social network.

🎮Real-world scenario 3: Geographical analysis where we need to identify islands within lakes within continents. The grid representations would be analogous to land/water mappings.

💡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.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

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: September 14, 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

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

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Count Sub 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?