6. Find the Number of Islands

The problem can be found at the following link: Question Link

Problem Description

Given a grid of size n*m (where n is the number of rows and m is the number of columns in the grid) consisting of '0's (Water) and '1's (Land), find the number of islands. An island is a group of connected '1's that are surrounded by water or the grid boundary. The connection can be vertical, horizontal, or diagonal.

Note:

• Islands are connected in all 8 possible directions: left, right, up, down, and the 4 diagonal directions.

• The entire grid is traversed, and the number of distinct islands is counted.

Example:

Input 1:

grid = [[0, 1],
        [1, 0],
        [1, 1],
        [1, 0]]

Output 1: 1

Explanation: All land cells are connected to form a single island.

---

Input 2:

grid = [[0, 1, 1, 1, 0, 0, 0],
        [0, 0, 1, 1, 0, 1, 0]]

Output 2: 2

Explanation: There are two islands, one formed by the group of '1's in the first three columns and another formed by the group of '1's in the sixth column.

---

My Approach

1. Depth-First Search (DFS):

   • We treat the grid as a graph and explore all connected cells containing '1' using DFS.

   • For each unvisited land cell, we perform a DFS to mark all connected land cells as visited. This entire DFS traversal is considered as one island.

   • Repeat the process for each unvisited land cell until all cells are checked.

2. Checking Boundaries:

   • The isValid() function ensures that the current cell lies within the grid boundaries and contains a '1' before proceeding with DFS.

3. DFS Traversal:

   • For each unvisited land cell, mark it as visited by setting it to '0'. Then, explore all 8 neighboring cells (horizontal, vertical, diagonal). If a neighboring cell is also land, continue the DFS from that cell.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n*m), where n is the number of rows and m is the number of columns in the grid. This is because we visit each cell once and traverse its neighbors.

• Expected Auxiliary Space Complexity: O(n*m), as the DFS call stack can grow up to the total number of cells in the grid in the worst case.

---

Code (C++)

class Solution {
public:
    vector<int> dx = {-1, 0, 1, 0, 1, -1, -1, 1};
    vector<int> dy = {0, -1, 0, 1, 1, 1, -1, -1};

    bool isValid(int x, int y, int n, int m) {
        return (x >= 0 && x < n && y >= 0 && y < m);
    }

    void dfs(int x, int y, vector<vector<char>>& grid, int n, int m) {
        grid[x][y] = '0';

        for (int k = 0; k < 8; k++) {
            int newX = x + dx[k];
            int newY = y + dy[k];

            if (isValid(newX, newY, n, m) && grid[newX][newY] == '1') {
                dfs(newX, newY, grid, n, m);
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int ans = 0;

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

---

Code (Java)

class Solution {

    private int[] dx = {-1, 0, 1, 0, 1, -1, -1, 1};
    private int[] dy = {0, -1, 0, 1, 1, 1, -1, -1};

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;

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

    private void dfs(int x, int y, char[][] grid, int n, int m) {
        grid[x][y] = '0';  // Mark the current cell as visited

        for (int k = 0; k < 8; k++) {
            int newX = x + dx[k];
            int newY = y + dy[k];

            if (isValid(newX, newY, n, m) && grid[newX][newY] == '1') {
                dfs(newX, newY, grid, n, m);
            }
        }
    }

    private boolean isValid(int x, int y, int n, int m) {
        return (x >= 0 && x < n && y >= 0 && y < m);
    }
}

---

Code (Python)

class Solution:
    def numIslands(self, grid):
        n = len(grid)
        m = len(grid[0])
        ans = 0

        dx = [-1, 0, 1, 0, 1, -1, -1, 1]
        dy = [0, -1, 0, 1, 1, 1, -1, -1]

        def dfs(x, y):
            grid[x][y] = 0
            for k in range(8):
                newX = x + dx[k]
                newY = y + dy[k]
                if is_valid(newX, newY) and grid[newX][newY] == 1:
                    dfs(newX, newY)

        def is_valid(x, y):
            return 0 <= x < n and 0 <= y < m

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    ans += 1
                    dfs(i, j)

        return ans

---

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit my LinkedIn: Any Questions. Thank you for your input; together, we strive to create a space where learning is a collaborative endeavor.

⭐ Star this repository if you find it helpful or intriguing! ⭐

---

📍Visitor Count