TLDR

1. Welcome!

2.  Read Unbiased News

   Interacting with our sponsors helps keep the newsletter free ❤️ 

3. Recommendations I live by!

4. Self-Gaslight of the week

5. JOBS & SCHOLARSHIPS

Day 3 : Flood Fill

Given an m x n integer grid image, where image[i][j] represents pixel values, and three integers sr, sc, and color.

Perform a flood fill starting from pixel image[sr][sc]. 

Change the color of the starting pixel and all 4-directionally connected pixels of the same color to the new color. 

Return the modified image after applying the flood fill.

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 of colors.

But remember, an adjacency matrix is just a way to represent relationships or connections between elements—in this case, the neighboring pixels that share the same value. 

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 BFS approach.

A Breath-First Search approach uses a queue to explore nodes level by level.

We will start by pushing the initial node (starting pixel) into the queue. In this problem, the starting node corresponds to the pixel located at (sr, sc) and mark the position as visited.

q.push({sr,sc});
visited[sr][sc] = true; 

For each element in the queue:

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. Update and Enqueue: If all conditions are met, update the neighbor's value to the new color and enqueue it

Once the queue is empty, the BFS is complete. Resulting in having our matrix, completely updated!!

Complete code:

 
class Solution {
public:
    vector<vector<bool>> visited; 
    bool isSafe (vector<vector<int>>& image, int sr, int sc,  int oldColor){ // Safe to move in the matrix 
        return (sr>-1&& sr<image.size() && sc>-1 && sc<image[sr].size() && image[sr][sc]==oldColor && visited[sr][sc]==false) ;
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(image.empty()){
            return image; 
        }
        visited = vector<vector<bool>>(image.size(), vector<bool>(image[0].size(), false));
        queue<pair<int,int>>q; 
        q.push({sr,sc});
        visited[sr][sc] = true; 
        int oldColor = image[sr][sc];
        vector<int>rowN = {-1,0,1,0};
        vector<int>colN = {0,1,0,-1};

        while(!q.empty()){
            pair<int,int> current = q.front(); 
            q.pop();
            visited[current.first][current.second] = true; 
            image[current.first][current.second] = color;
            for(int x=0; x<4; x++){
                int newRow = current.first+ rowN[x]; 
                int newCol = current.second + colN[x];
                if(isSafe(image, newRow, newCol, oldColor)){
                    q.push({newRow,newCol});
                }
            }

        }
        return image;
    }
    
};

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. DO NOT BECOME THE MAIN CHARACTER, BECOME THE DIRECTOR OF YOUR LIFE!!!

2. Gaslight yourself into walking a marathon with a walking desk.

Jobs and Scholarships

1. List of more scholarships!

2. Entry level jobs!!