Efficient Flood Fill Algorithm in TypeScript: A Step-by-Step Guide

Step-by-Step Solution to Replace Colors in a 2D Matrix Using Depth-First Search

Problem

Given a 2-D matrix representing an image, a location of a pixel in the screen and a color C, replace the color of the given pixel and all adjacent same colored pixels with C.

For example, given the following matrix, and location pixel of (2, 2), and ‘G’ for green:

B B W
W W W
W W W
B B B

Becomes

B B G
G G G
G G G
B B B

Flood Fill Algorithm in TypeScript

Flood fill is a classic algorithm used in computer graphics to determine the area connected to a given node in a multi-dimensional array. It is widely used in image editing software to implement the “bucket fill” tool, which fills a connected area with a single color.

Problem Explanation

Given a 2-D matrix representing an image, a location of a pixel in the screen, and a color C, we need to replace the color of the given pixel and all adjacent same-colored pixels with C.

Here’s the provided matrix and parameters:

Matrix:

B B W
W W W
W W W
B B B

Starting pixel location: (2, 2) New color: ‘G’ (Green) After applying the flood fill algorithm, the matrix should transform into:

B B G
G G G
G G G
B B B

Step-by-Step Solution

  1. Identify the Original Color: The color of the pixel at the given location.
  2. Edge Cases: If the color to be changed is the same as the new color, return the matrix as is.
  3. Use Depth-First Search (DFS): Recursively change the color of the starting pixel and its adjacent pixels (up, down, left, right) if they have the same color as the original pixel.

TypeScript Solution

Here’s the implementation in TypeScript:

function floodFill(matrix: string[][], sr: number, sc: number, newColor: string): string[][] {
    const originalColor = matrix[sr][sc];
    if (originalColor === newColor) return matrix;

    const rows = matrix.length;
    const cols = matrix[0].length;

    function dfs(r: number, c: number) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r][c] !== originalColor) {
            return;
        }

        matrix[r][c] = newColor;

        // Recursively apply DFS in all 4 directions
        dfs(r + 1, c); // down
        dfs(r - 1, c); // up
        dfs(r, c + 1); // right
        dfs(r, c - 1); // left
    }

    dfs(sr, sc);
    return matrix;
}

// Example usage
const image = [
    ['B', 'B', 'W'],
    ['W', 'W', 'W'],
    ['W', 'W', 'W'],
    ['B', 'B', 'B']
];

const startRow = 2;
const startCol = 2;
const newColor = 'G';

const result = floodFill(image, startRow, startCol, newColor);
console.log(result);

Explanation

  1. Original Color Identification: We first identify the original color of the pixel at the given location. If the original color is the same as the new color, we simply return the matrix as no changes are needed.
  2. DFS Function: The DFS function changes the color of the current pixel and recursively does the same for all its adjacent pixels (up, down, left, right) if they match the original color.
  3. Boundary Checks: Ensure that the DFS doesn’t go out of the matrix boundaries.

“Transformation often begins with the smallest pixel.” — Burhanuddin Mulla Hamzabhai

By following this guide, you will be able to implement the flood fill algorithm in TypeScript, enabling efficient image processing and manipulation techniques.

If you like this, please think about buying me a coffee! ☕️.

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go: