Flood Fill

Given a row and col index , get its value and change all the connected same value with provided color

Flood Fill

Problem Statement

You are given an image represented as an m x n grid of integers, image, where image[i][j] is the pixel value at that position. You are also given three integers: sr, sc, and color.

Your task is to perform a flood fill on the image, starting from the pixel at image[sr][sc].

To perform a flood fill:

• Start with the given pixel, and change its color to color.
• Do the same for every pixel that is directly adjacent (sharing a side, either horizontally or vertically) to the pixel you just changed, as long as it shares the same original color as the starting pixel.
• Keep repeating this for the neighbors of each newly updated pixel, as long as they still match the original starting color.
• Stop once there are no more matching adjacent pixels left to update.

Return the image after the flood fill is complete.

Examples

Example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

Output: [[2,2,2],[2,2,0],[2,0,1]]

Explanation: Starting from position (sr, sc) = (1, 1), every pixel connected to it by a path of the same original color gets updated to the new color. The bottom corner pixel is not changed, since it is not horizontally or vertically connected to the starting pixel (only diagonally).

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

Output: [[0,0,0],[0,0,0]]

Explanation: The starting pixel already has the color 0, which is the same as the target color. So no changes are made at all.

Constraints

• m == image.length
• n == image[i].length
• 1 ≤ m, n ≤ 50
• 0 ≤ image[i][j], color < 2¹⁶ (this value looked garbled in the original text as "216" — it most likely means 2¹⁶, a common way LeetCode phrases pixel value ranges, but you may want to double-check the original source)
• 0 ≤ sr < m
• 0 ≤ sc < n

Solution

We solve this using a simple backtracking / flood-fill traversal, spreading outward from the starting pixel in all four directions.

Steps

• First, we check the pixel's current color. If it's already the same as the target color, there's nothing to do — we return the image unchanged right away. This avoids an infinite loop, since otherwise the fill would keep "spreading" over already-matching pixels forever.
• We use a helper function, backtrack(i, j):
  • If (i, j) is out of bounds, or the pixel at this position does not match the original color (old), we stop here and return, since this pixel isn't part of the region we're filling.
  • Otherwise, we update this pixel to the new color.
  • We then call backtrack on all four neighboring directions: down, up, right, and left.
• We start the whole process by calling backtrack(sr, sc).
• Once the recursion finishes spreading through the entire connected region, we return the modified image.

Code

var floodFill = function (image, sr, sc, color) {

    let n = image.length;
    let m = image[0].length;
    let old = image[sr][sc];
    if (old === color) return image;

    function backtrack(i, j) {
        if (i < 0 || i >= n || j < 0 || j >= m || image[i][j] !== old)
            return;

        image[i][j] = color;
        backtrack(i + 1, j);
        backtrack(i - 1, j);
        backtrack(i, j + 1);
        backtrack(i, j - 1);
    }

    backtrack(sr, sc);

    return image;
};