What is the time complexity of Number of Islands?

The optimal solution has a time complexity of O(M*N).

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

Insight 1: The core idea is to traverse the grid and, upon encountering a '1', increment the island count and then 'sink' the entire island by marking all connected '1's as '0'. This avoids recounting the same island multiple times. Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are effective algorithms for traversing and marking connected components in a graph or a grid. The provided solutions use BFS.

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

Number of Islands - LeetCode 200 Solution

Q: What is the space complexity of Number of Islands?

The space complexity is O(M*N).

Q: Which companies ask LeetCode 200. Number of Islands in interviews?

This problem is frequently asked at Akuna Capital, Anduril, Axon, BILL Holdings, Barclays and 71 more companies.

Number of Islands - Complete Solution Guide

Number of Islands is LeetCode problem 200, 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 an m x n 2D binary grid grid which represents a map of '1' s (land) and '0' s (water), return the number of islands . An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Example 2: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"]

Detailed Explanation

The problem asks us to find the number of 'islands' in a 2D grid where '1' represents land and '0' represents water. An island is defined as a group of connected '1's (land) horizontally or vertically. The entire grid is surrounded by water, meaning any land touching the edges of the grid is part of an island.

Solution Approach

The provided solutions use a Breadth-First Search (BFS) approach. The algorithm iterates through each cell of the grid. If a cell contains a '1' (land), it means we've found a new island. We increment the island count, then initiate a BFS to explore all connected land cells. During the BFS, each visited '1' is marked as '0' to prevent it from being visited again. The BFS continues until all connected land cells of the current island have been visited and marked.

Step-by-Step Algorithm

Step 1: Iterate through each cell of the grid using nested loops.
Step 2: If a cell contains '1' (land), increment the island count.
Step 3: Mark the current cell as '0' (sink the land).
Step 4: Create a queue (using collections.deque in Python, LinkedList in Java, queue in C++) and add the coordinates of the current cell to the queue.
Step 5: While the queue is not empty, do the following:
Step 6: Dequeue a cell (row, col) from the queue.
Step 7: Explore the four neighboring cells (up, down, left, right).
Step 8: For each neighbor, check if it's within the grid boundaries and if it contains '1' (land).
Step 9: If a neighbor is land, mark it as '0' and enqueue its coordinates.
Step 10: After the BFS is complete for the current island, the outer loops continue iterating through the grid.
Step 11: Return the total island count.

Key Insights

Insight 1: The core idea is to traverse the grid and, upon encountering a '1', increment the island count and then 'sink' the entire island by marking all connected '1's as '0'. This avoids recounting the same island multiple times.
Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are effective algorithms for traversing and marking connected components in a graph or a grid. The provided solutions use BFS.
Insight 3: Modifying the input grid in place (changing '1' to '0') is a common optimization to avoid using extra space for tracking visited cells. However, this approach mutates the input, which might not be desirable in all situations.

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: Akuna Capital, Anduril, Axon, BILL Holdings, Barclays, BitGo, BlackRock, Booking.com, ByteDance, Capital One, Cisco, Citadel, Cloudflare, Comcast, Coupang, CrowdStrike, Disney, Docusign, DoorDash, Dropbox, EarnIn, Expedia, Flipkart, Goldman Sachs, Grammarly, HPE, HashedIn, Hotstar, Huawei, Infosys, Intel, Intuit, Karat, LinkedIn, Lucid, Moloco, Morgan Stanley, Nutanix, Nvidia, OKX, Oracle, Palantir Technologies, PayPal, PhonePe, Pinterest, Qualcomm, Reddit, Rivian, SAP, Salesforce, Samsung, ServiceNow, Siemens, Snap, Snowflake, SoFi, Tesla, Tinkoff, Turing, UiPath, Urban Company, Visa, Walmart Labs, Waymo, Whatnot, Wix, X, Yandex, Zenefits, Zepto, Zeta, Zillow, Zoho, Zomato, eBay, thoughtspot.

Number of Islands | LeetCode 200

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.LinkedList;
import java.util.Queue;

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        int num_islands = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    num_islands++;
                    grid[r][c] = '0';
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{r, c});
                    while (!queue.isEmpty()) {
                        int[] current = queue.poll();
                        int row = current[0];
                        int col = current[1];
                        for (int[] direction : new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {
                            int dr = direction[0];
                            int dc = direction[1];
                            int nr = row + dr;
                            int nc = col + dc;
                            if (0 <= nr && nr < rows && 0 <= nc && nc < cols && grid[nr][nc] == '1') {
                                grid[nr][nc] = '0';
                                queue.offer(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
        }
        return num_islands;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

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

Topics

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

Companies

Akuna CapitalAndurilAxonBILL HoldingsBarclaysBitGoBlackRockBooking.com

Stats

Difficulty:Medium

Languages:4

Companies:76

Problem #:200

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

11 steps

1
Step 1: Iterate through each cell of the grid using nested loops.
2
Step 2: If a cell contains '1' (land), increment the island count.
3
Step 3: Mark the current cell as '0' (sink the land).
4
Step 4: Create a queue (using collections.deque in Python, LinkedList in Java, queue in C++) and add the coordinates of the current cell to the queue.
5
Step 5: While the queue is not empty, do the following:
6
Step 6: Dequeue a cell (row, col) from the queue.
7
Step 7: Explore the four neighboring cells (up, down, left, right).
8
Step 8: For each neighbor, check if it's within the grid boundaries and if it contains '1' (land).
9
Step 9: If a neighbor is land, mark it as '0' and enqueue its coordinates.
10
Step 10: After the BFS is complete for the current island, the outer loops continue iterating through the grid.
11
Step 11: Return the total 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 time complexity is O(M*N) because we visit each cell in the grid at most once. The space complexity is O(M*N) because, in the worst-case scenario where the entire grid is an island, the queue in the BFS algorithm might contain all the cells of the grid.

📖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

Depth-First Search (DFS)

Instead of BFS, we can use DFS to explore the connected components. The logic is similar: when we find a '1', increment the island count and then recursively call DFS to 'sink' all connected '1's.

Time: O(M*N)Space: O(M*N) in the worst case (due to recursion stack), but on average it can be less than BFS if islands are smaller and more spread out.

Trade-offs: DFS can lead to stack overflow errors for very large grids with deep islands, whereas BFS generally avoids this issue due to iterative approach. However, DFS might be slightly simpler to implement.

Union Find (Disjoint Set)

Treat each '1' as a node and connect adjacent '1's using the union operation. The number of connected components (islands) can then be determined by finding the number of distinct roots.

Time: O(M*N * α(M*N)), where α is the inverse Ackermann function, which grows very slowly and is practically constant.Space: O(M*N) to store the parent array for the Union Find data structure.

Trade-offs: Union Find is more complex to implement than BFS or DFS. While its amortized time complexity is theoretically better, the difference is usually negligible in practice for typical grid sizes. Union Find can be more efficient if you need to perform many union/find operations over time, for example, if the grid is dynamically updated with new lands appearing.

✨

Key Insights

1Insight 1: The core idea is to traverse the grid and, upon encountering a '1', increment the island count and then 'sink' the entire island by marking all connected '1's as '0'. This avoids recounting the same island multiple times.
2Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are effective algorithms for traversing and marking connected components in a graph or a grid. The provided solutions use BFS.
3Insight 3: Modifying the input grid in place (changing '1' to '0') is a common optimization to avoid using extra space for tracking visited cells. However, this approach mutates the input, which might not be desirable in all situations.

📚

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 (either no rows or no columns). The solution correctly handles this by returning 0 since there are no islands.
Edge case 2: A grid filled entirely with '0's (water). The solution will iterate through the grid without finding any '1's, so the island count will remain 0, which is correct.
Edge case 3: A grid filled entirely with '1's (one large island). The solution will correctly identify this as a single island.
Edge case 4: Input grid containing non '0' or '1' characters. The provided solutions assume the grid contains only '0' and '1'. If other characters exist, the solutions might give incorrect results or encounter errors. This should be validated before island counting.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to mark visited cells (either with '0' or using a separate visited matrix). This will lead to infinite loops and incorrect island counts.

✗Common mistake 2: Not checking boundaries when exploring neighbors. This will cause array out-of-bounds errors.

✗Common mistake 3: Incorrectly implementing BFS or DFS, leading to incomplete traversal of islands.

✗Common mistake 4: Forgetting to handle the empty grid case. The code should correctly return 0 when the grid is empty.

✅

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 connected regions in an image (e.g., detecting objects in a binary image). The '1's could represent pixels belonging to an object, and the '0's represent the background.

🏦Real-world scenario 2: Network analysis - Determining the number of disconnected components in a network. The '1's could represent connections between nodes, and the '0's represent the absence of connections.

🎮Real-world scenario 3: Maze solving - Finding paths through a maze. The '1's could represent open paths, and '0's could represent walls. The algorithm can find connected open paths to determine if there is a path from start to finish.

📱Real-world scenario 4: Clustering - Grouping similar data points together. In a grid, adjacent data points that meet a similarity criteria can be considered part of the same cluster.

💡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

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ 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: June 21, 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

❓

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 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?