Solving Flood Fill - LeetCode problem

#programming #algorithms #leetcode #learning

Originally published on my Hashnode blog — cross-posted here for the Dev.to community.

In this problem, we delve into the Flood Fill algorithm, which plays a crucial role in tracing bounded areas with the same color. This algorithm finds applications in various real-world scenarios, such as the bucket-filling tool in painting software and the Minesweeper game.

https://leetcode.com/problems/flood-fill/description/

Problem Description

Given a 2D matrix, along with the indices of a source cell mat[x][y] and a target color C, the task is to color the region connected to the source cell with color C. The key idea here is to view the matrix as an undirected graph and find an efficient way to traverse it. Importantly, the movement is restricted to adjacent cells in four directions (up, down, left, and right).

Breadth-First Search (BFS) Approach

One way to solve this problem is to employ a Breadth-First Search (BFS) using a queue. Here's the step-by-step process:

Start by inserting the source cell into the queue and change its color to C.
While the queue is not empty:

* Pop the next element from the queue.

* Change the color of the current cell to `C`.

* Calculate the coordinates of the neighboring cells in all four directions.

* If any neighboring cell has the same color, insert it into the queue.

Time Complexity (TC): O(N*M) where N and M are the dimensions of the matrix.

Depth-First Search (DFS) Approach

Alternatively, you can implement the Depth-First Search (DFS) approach, which uses recursion:

Begin by changing the color of the source cell to C.
Calculate the coordinates of the neighboring cells in all four directions.
If any neighboring cell has the same color, recursively call the function on that cell until the base case is satisfied.

Time Complexity (TC): O(N*M) Space Complexity (SC): *O(N**M)

 let dx = [-1, 0, 1, 0];
 let dy = [0, 1, 0, -1];

const isValid = (x, y, image) => {
    let rows = image.length;
    let cols = image[0].length;
    if (x >= rows || y >= cols || x < 0 || y < 0) return false;
    return true;
};


const colorCell = (image,x,y,color, current_color) => {
   if(!isValid(x,y,image)) return;
   if(image[x][y] !== current_color) return;
   if(image[x][y] === color) return;
   image[x][y] = color;
   for(let i=0; i<4; i+=1) {
       let u = dx[i] + x;
       let v = dy[i] + y;
       colorCell(image, u, v, color, current_color);
   }
}

var floodFill = function(image, sr, sc, color) {
    colorCell(image, sr, sc, color, image[sr][sc]);
    return image;
};