Katkat
Back

Implement flood fill using BFS and DFS

AppleSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement graph traversal algorithms (BFS and DFS) on a 2D grid, focusing on boundary conditions and state management.

Problem Statement

Given a 2D integer grid image where each cell represents the pixel value of the image, and three integers sr, sc, and color, perform a flood fill on the image.

To perform a flood fill, start at the pixel (sr, sc) and all pixels connected 4-directionally to the starting pixel that have the same color as the starting pixel. Replace the color of all such pixels with color.

Implement two functions:

  1. floodFillDFS(image, sr, sc, color): Using recursion.
  2. floodFillBFS(image, sr, sc, color): Using an iterative queue.

Constraints

  • m == image.length, n == image[0].length
  • 1 <= m, n <= 50
  • 0 <= image[r][c] < 65536
  • 0 <= sr < m, 0 <= sc < n

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: The starting pixel is (1,1). All connected pixels with the value 1 are changed to 2.

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

Edge Cases

  • What happens if the target color is the same as the starting pixel's color?
  • Handling out-of-bounds indices.

Hints

Hint 1

Before traversing, save the original color of the starting pixel to identify which neighbors to change.

Hint 2

If the original color is already equal to the target color, return the image immediately to avoid an infinite recursion loop.

Hint 3

For BFS, use a queue to store coordinates and process them level-by-level, ensuring you mark cells as visited or change their color to prevent re-processing.

Follow-up questions

  • How would you modify these algorithms to handle 8-directional connectivity instead of 4-directional?
  • What is the space complexity of your DFS approach in the worst case, and how does it compare to the BFS approach?
  • If the image was extremely large (e.g., 10,000 x 10,000), how might you optimize the memory usage or handle potential stack overflow in DFS?