algoadvance

Leetcode 733. Flood Fill

Problem Statement

The problem description for Flood Fill on LeetCode is as follows:

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
Output: [[2,2,2],[2,2,2]]

Constraints:

Clarifying Questions

  1. Input Image Size: Can the image be of any size within the constraints?
    • Yes, the image size is bounded by the constraints (1 <= m, n <= 50).
  2. Pixel Values: What is the range of the pixel values in the image?
    • Each pixel value will be between 0 and 65535.
  3. Color to Replace: Should we handle the case where the starting pixel’s color is the same as the new color?
    • Yes, if image[sr][sc] is already equal to newColor, no changes should be made to avoid infinite loops.

Strategy

We can solve this problem using Depth-First Search (DFS) or Breadth-First Search (BFS). Here’s a high-level plan for using DFS:

  1. Base Case: If image[sr][sc] is already newColor, return the image as is.
  2. Recursive Filling: Implement a function to recursively change the color of the starting pixel and all connected pixels with the same color.
  3. Direction Handling: Use 4 directional vectors to handle the movement to neighboring pixels (up, down, left, right).

Code

Here is the Java implementation of the Flood Fill algorithm using DFS:

public class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int origColor = image[sr][sc];
        if (origColor != newColor) {
            dfs(image, sr, sc, origColor, newColor);
        }
        return image;
    }

    private void dfs(int[][] image, int i, int j, int origColor, int newColor) {
        if (i < 0 || i >= image.length || j < 0 || j >= image[0].length || image[i][j] != origColor) {
            return;
        }

        // Change the color
        image[i][j] = newColor;

        // Explore the neighbors (up, down, left, right)
        dfs(image, i - 1, j, origColor, newColor);
        dfs(image, i + 1, j, origColor, newColor);
        dfs(image, i, j - 1, origColor, newColor);
        dfs(image, i, j + 1, origColor, newColor);
    }
}

Time Complexity

This code ensures that all applicable pixels are updated while avoiding unnecessary modifications if the starting pixel is already newColor.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI