DevExCode

LeetCode 200: Number of Islands Solution

Master LeetCode problem 200 (Number of Islands), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use Depth First Search (DFS) to explore the grid. We will iterate through each cell in the grid and whenever we encounter a '1' (land), we will mark it as visited and perform a DFS to explore all adjacent land cells connected to it. By doing this, we can identify each island and count the total number of islands in the grid.

Detailed steps:

  1. Iterate through each cell in the grid.
  2. If the cell is unvisited and contains '1', increment the island count and perform DFS to mark all connected land cells as visited.
  3. In the DFS function, recursively explore all adjacent land cells and mark them as visited.
  4. Continue iterating through the grid until all cells have been visited.

Time Complexity: O(m*n) where m is the number of rows and n is the number of columns in the grid.

Space Complexity: O(m*n) for the recursive stack space.

Solution Code

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int count = 0;
        int m = grid.length;
        int n = grid[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return count;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        
        grid[i][j] = '0';
        
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 200 (Number of Islands)?

This page provides optimized solutions for LeetCode problem 200 (Number of Islands) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 200 (Number of Islands)?

The time complexity for LeetCode 200 (Number of Islands) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 200 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 200 in Java, C++, or Python.

Back to LeetCode Solutions