Flood Fill Algorithm Implementation and Analysis

Flood fill is a classic graph traversal problem where we need to color all connected pixels of the same color as a starting pixel. This solution presents both BFS and DFS approaches with detailed complexity analysis and practical implementation considerations for technical interviews.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the input grid? (e.g., 1x1 to 100x100, or larger?)
2. Are we allowed to mutate the input grid in-place? (This affects space complexity and design choices.)
3. What should we return? The modified grid or just the count of changed pixels?
4. Can we assume that the starting coordinates (sr, sc) are valid indices in the grid?
5. Should we handle cases where the new color is the same as the original color?

Restatement in my own words: The flood fill problem asks us to change the color of all connected pixels that have the same initial color as a starting pixel (sr, sc) to a new specified color. The "connected" pixels are those that are adjacent (up, down, left, right) to each other and have the same original color.

Clarification of inputs, outputs, and constraints:

• Input: A 2D grid of integers representing pixel colors, a starting row index sr, a starting column index sc, and a new color value newColor
• Output: The modified grid with all connected pixels of the original color changed to the new color
• Constraints:
  • Grid dimensions: typically up to 100x100 (but could be larger)
  • Pixel values: integers (could be negative or large)
  • Starting coordinates are guaranteed to be valid indices
  • The new color can be the same as the original color

Assumptions I'm making:

• The grid is rectangular (all rows have the same length)
• Adjacency is only in 4 directions (up, down, left, right) - not diagonal
• We can safely mutate the input grid in-place for efficiency

Data shape and hidden structure: The problem represents a graph traversal scenario where:

• Each pixel is a node in an undirected graph
• Adjacent pixels with the same color form edges
• The connected component to be modified is a connected subgraph rooted at (sr, sc)
• This structure suggests using either BFS or DFS traversal to explore all connected pixels with the same original color

The problem has a clear graph structure where we're essentially finding and modifying all nodes in the connected component that contains the starting node.

2. Pattern Recognition

The most likely pattern here is Graph Traversal or Connected Components, specifically using Breadth-First Search (BFS) or Depth-First Search (DFS).

The wording that signals this pattern includes:

• "flood fill" - a classic graph traversal problem where we need to explore connected regions
• The requirement to "fill" or "color" all connected pixels with the same initial color
• The constraint that only 4-directionally adjacent pixels (up, down, left, right) are considered part of the connected component

This problem fits the graph traversal pattern because:

1. We have a 2D grid representing a graph where each cell is a node
2. Each node connects to its 4 adjacent neighbors (if they exist)
3. We need to traverse all nodes that are connected through valid adjacency relationships
4. The traversal should stop when we encounter pixels with different colors

The core insight needed to solve it is that this is fundamentally about finding and coloring all nodes in a connected component starting from a specific node, where the connectivity is defined by 4-directional adjacency and color equality.

This is not a dynamic programming problem, but rather a graph connectivity problem where we're essentially finding all nodes that form one connected component based on color similarity and spatial adjacency.

3. Approach Evolution

My first instinct is to use a depth-first search (DFS) or breadth-first search (BFS) approach because this problem is essentially about traversing connected pixels with the same color. However, that would be O(n²) in worst case if we're dealing with a large grid and each pixel needs to be checked, but that's not the real bottleneck here.

Let me think about how to optimize this. The key insight is that we're only changing pixels that are connected to the starting pixel and have the same original color. I notice that if I maintain a queue or stack for BFS/DFS, I can reduce it to O(n) where n is the number of pixels in the connected component.

The core insight here is that we're essentially doing a graph traversal where each pixel is a node and adjacent pixels (up, down, left, right) are connected edges. Since we're only changing pixels with the same original color, we can think of this as finding all pixels that form a connected component starting from (sr, sc) with the same color.

I'm going to go with a recursive DFS approach because it's more intuitive and cleaner to implement for this problem. The algorithm will:

1. Start at the given pixel (sr, sc)
2. Check if it has the original color
3. If yes, change it to newColor and recursively process its 4-connected neighbors
4. Stop when we hit pixels with different colors or go out of bounds

This approach is O(n) time where n is the number of pixels in the connected component, and O(k) space where k is the maximum recursion depth (which can be up to n in worst case).

The invariant that must hold is: at any point during traversal, we only process pixels that have the original color and are within bounds of the image grid.

Let me think about the iterative approach as an alternative - that would use a stack explicitly to avoid potential stack overflow for very large connected components, but for the scope of this problem it's not necessary.

The key optimization is avoiding redundant processing by only visiting each pixel once and maintaining the color constraint throughout traversal.

4. Data Structure Choice

For the flood fill problem, I'll use a Queue as my primary data structure for the BFS approach.

Primary Data Structures Used

1. Queue (LinkedList) - Used to implement breadth-first search traversal

   • Why needed: To process pixels in the correct order (FIFO) and ensure we explore all connected pixels with the same color
   • Time impact: O(1) for enqueue/dequeue operations
   • Space impact: O(w × h) in worst case where w and h are image dimensions

2. 2D Array (int[][]) - The input image itself

   • Why needed: To store and modify the pixel values during traversal
   • Time impact: O(1) for read/write operations at any position
   • Space impact: O(w × h) - this is the input space we must work with

Why This Choice Is Optimal

The Queue provides the perfect structure for BFS traversal where we want to process all pixels at distance k before moving to distance k+1. This ensures we fill connected regions correctly without missing any pixels.

The 2D array is the natural choice since:

• It's the input format we're working with
• We need to read and update pixel values in-place
• It provides direct O(1) access to any position

Helper Structure

I'm not using any additional helper structures beyond the queue and the input array itself. The solution maintains a clean O(w × h) space complexity where w × h represents the image dimensions.

This choice is optimal because:

• No extra memory overhead beyond what's necessary for the algorithm
• Queue operations are efficient and predictable
• The input array can be modified in-place to save space

5. Algorithm Walkthrough

Let me trace through the flood fill algorithm using a concrete example to demonstrate how it works step by step.

Consider the input grid:

[
  [1, 1, 1],
  [1, 1, 0],
  [1, 0, 1]
]

Starting at position (1,1) with original color 1 and new color 2.

Step 1: Begin at (1,1) with color 1. This matches our original color, so we process it.

• Add (1,1) to the queue
• Change grid[1][1] from 1 to 2

Step 2: Process queue element (1,1)

• Check neighbors: up(0,1) - color 1 ✓, down(2,1) - color 0 ✗, left(1,0) - color 1 ✓, right(1,2) - color 0 ✗
• Add (0,1) and (1,0) to queue
• No changes to grid yet

Step 3: Process queue element (0,1)

• Check neighbors: up(−1,1) - out of bounds ✗, down(1,1) - already processed ✓, left(0,0) - color 1 ✓, right(0,2) - color 1 ✓
• Add (0,0) and (0,2) to queue
• Change grid[0][1] from 1 to 2

Step 4: Process queue element (1,0)

• Check neighbors: up(0,0) - already processed ✓, down(2,0) - color 1 ✓, left(1,−1) - out of bounds ✗, right(1,1) - already processed ✓
• Add (2,0) to queue
• Change grid[1][0] from 1 to 2

Step 5: Process queue element (0,0)

• Check neighbors: up(−1,0) - out of bounds ✗, down(1,0) - already processed ✓, left(0,−1) - out of bounds ✗, right(0,1) - already processed ✓
• No new elements added to queue

Step 6: Process queue element (0,2)

• Check neighbors: up(−1,2) - out of bounds ✗, down(1,2) - color 0 ✗, left(0,1) - already processed ✓, right(0,3) - out of bounds ✗
• No new elements added to queue

Step 7: Process queue element (2,0)

• Check neighbors: up(1,0) - already processed ✓, down(3,0) - out of bounds ✗, left(2,−1) - out of bounds ✗, right(2,1) - color 0 ✗
• No new elements added to queue

Final Result:

[
  [2, 2, 2],
  [2, 2, 0],
  [2, 0, 1]
]

The algorithm correctly floods the connected region starting from (1,1) while respecting boundary conditions and avoiding reprocessing already-visited cells. The queue ensures we process cells in breadth-first order, which is essential for flood fill semantics.

Edge cases handled:

• Boundary conditions (out of grid bounds)
• Already-processed cells (via visited set)
• Color mismatch prevention
• Empty or single-cell grids

6. Java Solution

public class FloodFill {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        // Handle edge case of empty image
        if (image == null || image.length == 0 || image[0].length == 0) {
            return image;
        }
        
        int originalColor = image[sr][sc];
        
        // If new color is same as original, no need to process
        if (originalColor == newColor) {
            return image;
        }
        
        // Perform DFS to flood fill
        dfs(image, sr, sc, originalColor, newColor);
        
        return image;
    }
    
    private void dfs(int[][] image, int row, int col, int originalColor, int newColor) {
        // Base case: out of bounds
        if (row < 0 || row >= image.length || 
            col < 0 || col >= image[0].length) {
            return;
        }
        
        // Base case: not the original color to be replaced
        if (image[row][col] != originalColor) {
            return;
        }
        
        // Change the color
        image[row][col] = newColor;
        
        // Recursively process 4-directional neighbors
        dfs(image, row - 1, col, originalColor, newColor); // up
        dfs(image, row + 1, col, originalColor, newColor); // down
        dfs(image, row, col - 1, originalColor, newColor); // left
        dfs(image, row, col + 1, originalColor, newColor); // right
    }
}

This solution uses depth-first search (DFS) with recursion to implement the flood fill algorithm. The key insight is that we only need to change pixels that are connected to the starting pixel and have the same original color. The DFS explores all valid neighboring pixels in four directions (up, down, left, right) until it reaches pixels that don't match the original color or go out of bounds.

7. Complexity Analysis

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns in the image grid.

Each cell in the image grid is visited at most once during the flood fill operation. Even though we use a queue-based BFS approach, in the worst case where all cells need to be filled, we process each cell exactly once. The operations performed at each cell (checking color, adding to queue) are O(1), making the overall time complexity linear with respect to the total number of pixels.

Space Complexity: O(m × n) in the worst case for the queue storage and visited set.

In the worst-case scenario where all pixels need to be filled, our queue can grow to contain all pixels in the image grid. Additionally, we maintain a visited set that stores up to m × n elements. The space complexity is therefore proportional to the total number of pixels in the image.

The solution is optimal for this problem because:

1. We must examine each pixel at least once to determine whether it should be filled
2. The flood fill operation requires visiting connected pixels, which inherently needs to process all affected cells
3. Our approach avoids redundant visits by using a visited set, ensuring each cell is processed exactly once

The complexity analysis assumes that the image dimensions are bounded and that basic operations like queue insertion/deletion and set membership checks are O(1) amortized time. In practice, these operations scale linearly with the number of elements in the queue or set, but since we're processing each element once, the overall complexity remains linear.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty image: Handle null or empty 2D array gracefully
• Single pixel image: 1x1 grid should work without issues
• Single row/column: Ensure boundary checks don't break

Duplicate Values and Repeated States

• Same color target: When newColor equals oldColor, the algorithm should terminate immediately without infinite loops
• Repeated flood fill: The visited tracking prevents revisiting pixels, avoiding cycles in connected components

Boundary Conditions

• Boundary pixel flood: Pixels at image borders (0,0) and (m-1,n-1) must not cause array index out of bounds
• Color matching at edges: Ensure color comparison works correctly for edge pixels

Common Implementation Mistakes

• Missing visited tracking: Without a visited set or boolean matrix, the algorithm may infinitely loop in connected components
• Incorrect boundary checks: Off-by-one errors in checking pixel coordinates can cause IndexOutOfBoundsException
• Color comparison logic: Not handling the case where newColor == oldColor properly can lead to unnecessary processing or incorrect behavior
• Recursive stack overflow: For large images, deep recursion can cause stack overflow; iterative approaches with explicit stacks are more robust

Implementation-specific Pitfalls

• Array indexing: Confusing row/column indices or treating them as x/y coordinates incorrectly
• State persistence: Not properly maintaining the flood fill state across recursive calls or stack operations
• Return value confusion: Misunderstanding whether to return the modified image or just modify in-place

9. Alternative Approaches

There are several alternative approaches to solving the flood fill problem, each with different trade-offs:

1. Iterative BFS/DFS using Queue/Stack: Instead of recursion, we can use an explicit queue or stack for iterative traversal. This approach avoids potential stack overflow issues with very large images and gives us more control over the traversal order. The time complexity remains O(m×n) but we eliminate the recursion overhead and stack space usage.

2. Union-Find (Disjoint Set): We could model this as a connected components problem where we union pixels with the same color that are adjacent. However, this approach is overkill for flood fill and would require additional preprocessing to identify connected components. It's O(m×n) time but with higher constant factors and more complex implementation.

3. Two-Pass Algorithm: Process the image in two passes - first identify all pixels that should be changed, then perform the actual color changes. This is useful when we want to minimize the number of times we access memory or when we're doing batch operations. However, it's less intuitive and adds complexity.

4. Multi-threaded Processing: For very large images, we could divide the image into regions and process them in parallel. This is more complex to implement correctly due to race conditions and requires careful synchronization, but can provide performance benefits in multi-core environments.

The chosen recursive DFS approach is preferred because it's the most intuitive, has clean implementation, and provides optimal time complexity for the problem constraints. The iterative approach is a reasonable alternative when stack overflow concerns are present, but the recursive solution is more readable and maintainable for typical use cases.

10. Test Cases

public class FloodFillTestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic flood fill
        int[][] image1 = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        int[][] result1 = new Solution().floodFill(image1, 1, 1, 2);
        // Expected: [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
        
        // Test Case 2: Single pixel
        int[][] image2 = {{0}};
        int[][] result2 = new Solution().floodFill(image2, 0, 0, 1);
        // Expected: [[1]]
        
        // Test Case 3: No change needed (new color same as original)
        int[][] image3 = {{0, 0, 0}, {0, 1, 1}};
        int[][] result3 = new Solution().floodFill(image3, 1, 1, 1);
        // Expected: [[0, 0, 0], [0, 1, 1]]
        
        // Test Case 4: Large image with multiple connected regions
        int[][] image4 = {
            {0, 0, 0, 0},
            {0, 1, 1, 0},
            {0, 1, 1, 1},
            {0, 0, 0, 0}
        };
        int[][] result4 = new Solution().floodFill(image4, 1, 1, 2);
        // Expected: [[0, 0, 0, 0], [0, 2, 2, 0], [0, 2, 2, 2], [0, 0, 0, 0]]
        
        // Test Case 5: Edge case - flood fill from corner
        int[][] image5 = {{1, 1, 0}, {1, 0, 0}, {0, 0, 0}};
        int[][] result5 = new Solution().floodFill(image5, 0, 2, 3);
        // Expected: [[1, 1, 3], [1, 3, 3], [0, 0, 0]]
        
        // Test Case 6: Empty image (edge case)
        int[][] image6 = {};
        int[][] result6 = new Solution().floodFill(image6, 0, 0, 1);
        // Expected: []
    }
}

Representative Sample Cases:

1. Basic flood fill: Standard 3x3 grid where connected pixels are filled
2. Single pixel: Edge case with minimal input size
3. No change needed: When target color equals original color

Tricky Case:

• Large image with multiple connected regions: Tests proper boundary handling and connectivity logic

Boundary Case:

• Empty image: Tests robustness against edge cases with zero dimensions

These test cases cover the core functionality while validating edge case handling and ensuring correctness across various input configurations.

11. Final Summary

The core insight is that flood fill can be efficiently solved using either BFS or DFS traversal from the starting pixel, systematically exploring connected pixels with the same color while maintaining a color replacement invariant. The solution works by leveraging graph traversal to identify all pixels that should be updated, ensuring we don't revisit already-processed pixels through careful state management. This approach is optimal with O(m×n) time complexity where m×n is the image dimensions, as we must potentially visit every pixel at least once to determine the connected component. The key efficiency comes from avoiding redundant traversals and using appropriate data structures (queue for BFS or recursion stack for DFS) to maintain the exploration order while ensuring correctness through proper boundary and color checking.