Flood Fill Algorithm Explanation

This problem requires us to implement the flood fill algorithm. Given a 2D array (image), a starting coordinate (sr, sc), and a color, we need to replace the color of the starting pixel and all connected pixels of the same color with the new color. Let's walk through a couple of approaches.

1. Naive Approach: Recursive Flood Fill

The most straightforward way to implement flood fill is by using recursion. We start at the given pixel, change its color, and then recursively call the flood fill function on its four neighbors (up, down, left, right) if they have the same original color as the starting pixel.

Algorithm:

1. Check if the starting pixel's color is the same as the new color. If so, return the original image (as per the problem description).
2. Define a recursive function floodFillUtil(image, row, col, newColor, originalColor).
3. In floodFillUtil:
   • Base Case: If row or col are out of bounds, or image[row][col] is not equal to originalColor, return.
   • Set image[row][col] to newColor.
   • Recursively call floodFillUtil on the four neighboring pixels: (row-1, col), (row+1, col), (row, col-1), (row, col+1).
4. Call floodFillUtil starting from (sr, sc) with the original color and the new color.
5. Return the modified image.

Code (Java):

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        floodFillUtil(image, sr, sc, color, originalColor);
        return image;
    }

    private void floodFillUtil(int[][] image, int row, int col, int newColor, int originalColor) {
        if (row < 0 || row >= image.length || col < 0 || col >= image[0].length || image[row][col] != originalColor) {
            return;
        }

        image[row][col] = newColor;

        floodFillUtil(image, row - 1, col, newColor, originalColor);
        floodFillUtil(image, row + 1, col, newColor, originalColor);
        floodFillUtil(image, row, col - 1, newColor, originalColor);
        floodFillUtil(image, row, col + 1, newColor, originalColor);
    }
}

Time Complexity: O(m * n)

In the worst case, we might have to visit every pixel in the image.

Space Complexity: O(m * n)

In the worst case, the recursion depth can be proportional to the number of pixels if the entire image has the same color, leading to a stack overflow.

2. Optimal Approach: Iterative Flood Fill (Using Queue)

To avoid potential stack overflow issues with the recursive approach, especially for large images, we can implement flood fill iteratively using a queue (Breadth-First Search).

Algorithm:

1. Check if the starting pixel's color is the same as the new color. If so, return the original image.
2. Create a queue and enqueue the starting pixel (sr, sc). Also, store the original color.
3. While the queue is not empty:
   • Dequeue a pixel (row, col) from the queue.
   • Change the color of image[row][col] to newColor.
   • Check the four neighbors of (row, col):
     • If a neighbor is within the bounds of the image and has the same original color, enqueue it.
4. Return the modified image.

Code (Java):

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }

        int rows = image.length;
        int cols = image[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = color; // Initial color change

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            int[] pixel = queue.poll();
            int row = pixel[0];
            int col = pixel[1];

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && image[newRow][newCol] == originalColor) {
                    image[newRow][newCol] = color;  // Change color here, before enqueuing
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }

        return image;
    }
}

Time Complexity: O(m * n)

In the worst case, we might have to visit every pixel in the image.

Space Complexity: O(m * n)

In the worst case, the queue can contain all the pixels in the image if the entire image has the same color.

Edge Cases:

• Starting pixel already has the target color: The algorithm should return the original image without modification.
• Image is empty: The algorithm should handle this gracefully (though constraints state m, n >= 1, so it won't happen).
• Invalid starting coordinates: The algorithm should handle out-of-bounds sr and sc (though constraints say 0 <= sr < m and 0 <= sc < n, so it won't happen).
• Color range: Ensure that the color values are handled correctly based on the specified constraints (0 <= image[i][j], color < 2¹⁶).

Both the recursive and iterative approaches have the same time complexity O(mn). The iterative version with a queue is generally preferred to avoid stack overflow for larger images. The space complexity is also O(mn) for both approaches in the worst case.