algoadvance

Leetcode 733. Flood Fill

Problem Statement

The problem “733. Flood Fill” requires you to implement the flood fill algorithm, which is a way to repaint a region in an image. Given a 2D image represented as a matrix of integers image, where image[row][col] represents the pixel value at the position (row, col), a starting pixel (sr, sc), and a new color newColor, you’re supposed to “flood fill” the image.

Flood fill means you need to start from the pixel (sr, sc) and replace all the adjacent pixels of the same color with newColor. Adjacent pixels are pixels that share one of the four cardinal directions (up, down, left, right).

Example:

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 starting pixel (1, 1) with pixel value 1, all the adjacent pixels with the same value are replaced by 2.

Clarifying Questions

  1. Clarify input edge cases: What should be done if image is empty or contains only one pixel?
  2. Overlapping colors: What if newColor is the same as the starting pixel color?
  3. Large Images: Are there any constraints on the size of the image to consider time and space optimization?

Strategy

  1. Base Case: If the color of the starting pixel (sr, sc) is already newColor, we can return the image as is to avoid unnecessary operations.
  2. Recursive Flood Fill: Use Depth-First Search (DFS) to explore all neighboring pixels. If a neighboring pixel has the same color as the starting pixel, change its color to newColor and recursively apply the same operation to its neighbors.
  3. Bounds Check: Ensure that the pixel coordinates are within the image boundaries during the DFS.

Code

Here’s how we can implement the flood fill algorithm in C++:

class Solution {
public:
    void floodFillDFS(vector<vector<int>>& image, int sr, int sc, int oldColor, int newColor) {
        // Base case: Check boundaries
        if (sr < 0 || sr >= image.size() || sc < 0 || sc >= image[0].size()) {
            return;
        }
        // If the pixel is not the old color, return
        if (image[sr][sc] != oldColor) {
            return;
        }
        
        // Update the color
        image[sr][sc] = newColor;
        
        // Recursively call floodFillDFS on all 4 adjacent pixels
        floodFillDFS(image, sr + 1, sc, oldColor, newColor);
        floodFillDFS(image, sr - 1, sc, oldColor, newColor);
        floodFillDFS(image, sr, sc + 1, oldColor, newColor);
        floodFillDFS(image, sr, sc - 1, oldColor, newColor);
    }
    
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if (image.empty() || image[0].empty()) return image;

        int oldColor = image[sr][sc];
        // If the old color is the same as the new color, don't do anything
        if (oldColor == newColor) return image;
        
        floodFillDFS(image, sr, sc, oldColor, newColor);
        
        return image;
    }
};

Explanation

  1. Base Check:
    • If the image is empty or newColor is the same as the existing color at (sr, sc), return the image directly.
  2. DFS Helper Function floodFillDFS:
    • Change the color of the current pixel.
    • Recursively apply the same operation to the four neighboring pixels if they have the same color as oldColor.

Time Complexity

This approach ensures that all connected pixels with the same original color are updated to the newColor efficiently.

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