🌱 Keegan's Digital Garden

200. Number of Islands

3 min read

📝 Problem Details

input matrix of size m x n input matrix is a binary grid 1s in the grid represent land 0s represent water return the number of “islands” island: surrounded by water and is formed by connecting adjacent lands horizontally or vertically

💭What Were My Initial Thoughts?

we need to keep track of adjacent / connecting elements of land 
performing a BFS on the neighbors of a given piece of land should construct a land mass
we can mark each piece of land as visited so not to reuse it in the future to construct a new land mass

💡 Explanation of Solution

same as initial thoughts

⌛ Complexity Analysis

Time Complexity: O(n*m) for linear traversal of grid
Space Complexity: O(min(n,m))
- BFS queue can hold up to min(m,n) elements in the worst case

💻 Implementation of Solution

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        
        // base case: grid is empty and there are no islands
        if(grid.empty()) return 0;
 
        // setup traversal variables
        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;
        
        vector<pair<int,int>> directions = 
        {
            {0,1},  // right
            {0,-1}, // left
            {1,0},  // up
            {-1,0}  // down
        };
 
        // traverse rows
        for(int r = 0; r < rows; r++) {
            // traverse columns
            for(int c = 0; c < cols; c++) {
                // check if the current element in the grid is an 'island'
                if(grid[r][c] == '1') {
                    // incrememnt count
                    count++;
                    // init a bfs queue upon encountering our first island
                    queue<pair<int,int>> q;
                    // push position of island into queue
                    q.push({r,c});
                    // change the value in the grid to zero to mark it as visited
                    grid[r][c] = 'x';
                    // bfs while loop for while the queue isnt empty
                    while(!q.empty()) {
                        // get the row and col values from the queue
                        auto [row, col] = q.front();
                        q.pop();
                        // try and see for each direction if there is also land
                        for(auto [directionRow, directionCol] : directions) {
                            // if there is push it into the queue and mark it as visited
                            int newRow = row + directionRow;
                            int newCol = col + directionCol;
                            if(newRow >= 0 && newRow < rows // in bounds?
                            && newCol >= 0 && newCol < cols // in bounds?
                            && grid[newRow][newCol] == '1') { // land?
                                q.push({newRow, newCol});
                                grid[newRow][newCol] = 'x'; // mark visited
                            }
                        }
                    }
                }
            }            
        }
        return count;
    }
};

Graph View