TLDR

1. Welcome!

2. Recommendations I live by!

3. Self-Gaslight of the week

4. JOBS & SCHOLARSHIPS

Day 4 : Number Of Islands

Given an m x n 2D binary grid where '1's represent land and '0's represent water.

Return the number of distinct islands formed by connected adjacent lands horizontally or vertically, assuming the grid edges are surrounded by water.

Before we dive in,

Breathe.

Let’s analyze the problem a bit, and note, how the problem is already giving us our adjacency matrix. 

Denisse, what do you mean? The problem is giving us a matrix.

But remember, an adjacency matrix is just a way to represent relationships or connections between elements—in this case, the neighbors are the cells adjacent.

Now, I will show you a trick to find the 4-directionally connected neighbors in any matrix.

This trick involves using two vectors to easily calculate the neighboring positions by adding specific values to the current row and column indices.

vector<int> rowN = {-1, 0, 1, 0}; // These represent changes in row positions (up, right, down, left)
vector<int> colN = {0, 1, 0, -1}; // These represent changes in column positions (up, right, down, left)

By adding those values you can find the 4-directionally connected neighbors.

But there is a catch. 

To ensure that we don’t go out of bounds when accessing neighbors in the matrix, we'll add a helper function called isSafe. This function will check whether a given neighbor is within the limits of the matrix.

Once we know how to find the neighbors, the magic happens. 🪄 

To find all the neighbors, we will use a DFS approach, (Check out last week’s BFS approach)

A Depth-First Search approach uses recursion to go through all of the connected land cells, marking them as visited to ensure each island is counted only once.

We will start at the index (0,0) and we will iterate through the entire matrix. If the value of the cell is 1 and we haven’t visited.

We will send the coordinates to our DFS function.

For each coordinate inside our DFS function, we will:

1. Mark as Visited: For the current node, mark it as visited.

2. Find Valid Neighbors: Use our directional trick with rowN and colN to locate the 4-directional neighbors.

3. Check Conditions: Use the isSafe function to ensure the neighbors are within boundaries, not visited, and have the old color.

4. Call DFS Recursively: For each valid neighbor, recursively call the DFS function to continue exploring the entire island.

Once we’ve explored the entire island, we will go back to our original iteration through the matrix and increment our variable numIslands to keep track of the number of distinct islands found.

We continue this process, exploring each unvisited land cell ('1') with DFS, until we have checked all cells in the matrix.

Complete code:

 
class Solution {
public:
    vector<vector<bool>> visited; 
    int colSize;
    int rowSize; 
    bool isSafe(int newRow, int newCol, vector<vector<char>>& grid){
        return (newRow < rowSize && newRow >= 0 && newCol < colSize && newCol >= 0 && grid[newRow][newCol] == '1' &&
         !visited[newRow][newCol]);
    }
    void DFS(int row, int col,vector<vector<char>>& grid){
        visited[row][col] = true; 
        vector<int> rowNeigh = { -1, 0, 1, 0 }; 
        vector<int> colNeigh = { 0, 1, 0, -1 };
        for(int x=0; x<4; x++){
        int newRow = row +rowNeigh[x]; 
        int newCol  = col + colNeigh[x];
        if(isSafe(newRow, newCol, grid) ){
            DFS( newRow, newCol,grid);
        }
    }
    }  

    int numIslands(vector<vector<char>>& grid) {

        rowSize = grid.size();  //m 
        colSize = grid[0].size();  //n 
        visited = vector<vector<bool>>(rowSize, vector<bool>(colSize, false));       
        int numIslands=0; 
        for(int row=0; row<grid.size(); row++){
            for(int col=0; col<grid[row].size(); col++){
                if(grid[row][col]=='1' && !visited[row][col]){
                    DFS(row,col, grid);
                    numIslands++;
                }

            }
        }
        return numIslands; 
    }
};

Recommendations

Level up your inbox by subscribing to what I am subscribed to!

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. Be the tortoise

2. The truth about Software Engineering

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!