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.

Clarifying Questions

  1. Can the grid be empty?
    • Yes, the grid can be empty.
  2. What is the maximum size of the grid?
    • There is no explicit maximum size constraint provided, but typical constraints would be around 300x300 for such problems in coding interviews.
  3. Are diagonally adjacent ‘1’s considered connected?
    • No, only horizontally or vertically adjacent ‘1’s are considered connected.

Code

#include <vector>
#include <queue>

class Solution {
public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
        
        int num_islands = 0;
        int rows = grid.size();
        int cols = grid[0].size();
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '1') {
                    // Found an island, start a BFS/DFS
                    num_islands++;
                    fill(grid, r, c);
                }
            }
        }
        
        return num_islands;
    }
    
private:
    void fill(std::vector<std::vector<char>>& grid, int r, int c) {
        int rows = grid.size();
        int cols = grid[0].size();
        std::queue<std::pair<int, int>> q;
        q.push({r, c});
        grid[r][c] = '0';  // mark as visited
        
        std::vector<std::pair<int, int>> directions = \{\{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [cur_r, cur_c] = q.front();
            q.pop();
            
            for (auto [dr, dc] : directions) {
                int new_r = cur_r + dr;
                int new_c = cur_c + dc;
                
                if (new_r >= 0 && new_r < rows && new_c >= 0 && new_c < cols && grid[new_r][new_c] == '1') {
                    q.push({new_r, new_c});
                    grid[new_r][new_c] = '0';  // mark as visited
                }
            }
        }
    }
};

Strategy

  1. Initialization: Start by checking if the grid is empty. If it is, return 0 islands.
  2. Iterate through grid: Loop through each cell in the grid:
    • If the cell contains a ‘1’, increment the island count and initiate a BFS or DFS to mark all adjacent ‘1’s as visited.
  3. BFS/DFS:
    • Use BFS (can also use DFS) to traverse all connected ‘1’s and mark them as ‘0’ (visited).
    • Use a queue to implement BFS, starting from the current cell.
    • Process each cell in the queue by marking it as visited and pushing its unvisited neighbors into the queue.
  4. End of Iteration: After the BFS/DFS completes for a starting ‘1’, continue to the next cell.
  5. Return Result: After iterating through the entire grid, return the total count of islands.

Time Complexity

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