algoadvance

Leetcode 200. Number of Islands

Problem Statement

Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count 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:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

Clarifying Questions

1. Grid size: Is there any constraint on the size of the grid?
   • The grid can be of any size, ranging from very small to quite large.
2. Modification allowed: Can we modify the input grid directly?
   • Yes, modifying the grid directly to mark visited cells is usually acceptable and helps in-space optimization.
3. Diagonal cells: Are diagonal connections considered?
   • No, only horizontal and vertical connections are considered.

Strategy

1. Traversal: Use Depth-First Search (DFS) to traverse and mark each part of an island.
2. Marking: Once a ‘1’ is found, start a DFS from that cell to mark all connected ‘1’s as visited (turn them into ‘0’s).
3. Count: Each DFS traversal from a start point (‘1’) increases the island count by one.

Code

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

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

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    numberOfIslands++;
                    dfs(grid, i, j);
                }
            }
        }

        return numberOfIslands;
    }

    private void dfs(char[][] grid, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Base case: if out of bounds or already visited
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
            return;
        }

        // Mark the cell as visited
        grid[i][j] = '0';

        // Visit all four adjacent cells
        dfs(grid, i + 1, j); // down
        dfs(grid, i - 1, j); // up
        dfs(grid, i, j + 1); // right
        dfs(grid, i, j - 1); // left
    }
}

Time Complexity

• Time Complexity: O(M * N), where M is the number of rows and N is the number of columns in the grid. This is because we visit every cell once.
• Space Complexity: O(M * N) in the worst case for the recursion stack, which occurs when the grid is filled with land cells.

Using Depth-First Search, we efficiently traverse and mark islands while keeping the algorithm’s complexity manageable.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?