Number of Islands (#200 Leetcode)

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"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

The piece of land is only vertically or horizontally connected but not diagonally. 

 

Method 1: DFS 

The idea is to go as deep into a graph as possible until a dead end is reached, at which point we backtrack and visit some other branch. 

Each node will be considered as x, y where x denotes row and y denotes column. As each node can be traversed 1 step horizontally and vertically, this can be achieved by visiting x-1, y (top), x+1, y (bottom),  x, y-1 (left), x, y+1 (right). 

1. If the node (0, 0) is 1, it can be an island. So, go deep and mark the entire island by following the above rule. 

2. Number of islands count will be incremented to 1.

3. Once one node is visited, it will be marked as 2/0 to differentiate from 1 (island). 

4. Visit the entire row by doing steps 1 to 3. After visiting the entire row, go to second row. If the node is 0/2, just skip and go to next node. 

Time Complexity is O(n) as each node can be visited 5 times in the worst case. 

1. One time while processing the node.

2. 4 times while processing the adjacent nodes. 

Space Complexity is O(1) considering the recursive calls will not take any extra space. 

But, in the worst case, each node can be an island, so the number of recursive calls would be O(m*n). In this case, recursive calls will be made in a snake order (row0(0->n-1), row1(0->n-1), .... rown-1(0->n-1))

Understand what is vector of vector too here.

class Solution {
public:
    void coverIslandArea(vector<vector<char>>& grid, int i, int j) {
        int rows = grid.size();
        int columns = rows ? grid[0].size() : 0;
        
        if (i < 0 || i >= rows || j < 0 || j >= columns || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        coverIslandArea(grid, i - 1, j);
        coverIslandArea(grid, i + 1, j);
        coverIslandArea(grid, i, j -1);
        coverIslandArea(grid, i, j + 1);
        return; 
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int islands = 0;
        int rows = grid.size();
        int columns = rows ? grid[0].size() : 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    coverIslandArea(grid, i, j);
                }
            }
        }
        return islands;
    }
};

Method 2: BFS 

Each time when I see a '1', I increment the counter and then erase all connected '1's using a queue.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0; 
        int islands = 0, offsets[] = {0, 1, 0, -1, 0};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    // Assign root node as discovered/visited.
                    grid[i][j] = '0';
                    queue<pair<int, int>> todo;
                    //Enqueue the node 
                    todo.push({i, j});
                    while (!todo.empty()) {
                        pair<int, int> p = todo.front();
                        // When Queue is not empty, dequeue the first element from the queue. 
                        todo.pop();
                        for (int k = 0; k < 4; k++) {
                            //  Find all edges/neighbours of this node
                            int r = p.first + offsets[k], c = p.second + offsets[k + 1];
                            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1') {
                                // If the edge is not discovered, make it as discovered. 
                                grid[r][c] = '0';
                                // Enqueue the vertex
                                todo.push({r, c});
                            }
                        }
                    }
                }
            }
        }
        return islands;
    }
};

References : Tech Dose