Welcome to AlgoCademy’s in-depth exploration of the Flood Fill algorithm! If you’re on a journey to enhance your coding skills, particularly in preparation for technical interviews at major tech companies, understanding Flood Fill is crucial. This powerful technique is not only a common interview question but also a fundamental concept in computer science with wide-ranging applications.
What is Flood Fill?
Flood Fill is an algorithm used to determine and modify connected regions in a multi-dimensional array. Imagine pouring water onto a flat surface with raised edges – the water would fill all connected areas. This is essentially what Flood Fill does in a digital context.
In programming terms, Flood Fill starts at a specific cell (often called the “seed”) and spreads to neighboring cells that meet certain criteria, typically having the same value or color. This process continues recursively or iteratively until all connected cells meeting the criteria have been visited and potentially modified.
Applications of Flood Fill
Before we dive into the implementation details, let’s explore some real-world applications of Flood Fill:
- Image Processing: Used in paint programs for the “bucket fill” tool.
- Game Development: Employed in games like Minesweeper to reveal empty cells.
- Maze Solving: Helps in finding paths through mazes or labyrinths.
- Segmentation: Used in image segmentation to separate different regions.
- Map Coloring: Assists in geographical map coloring algorithms.
Understanding the Algorithm
The Flood Fill algorithm typically works on a 2D grid or matrix, but it can be extended to higher dimensions. Here’s a step-by-step breakdown of how it operates:
- Choose a starting cell (seed point).
- Check if the current cell meets the filling criteria (e.g., same color as the target).
- If it meets the criteria, change its value (e.g., to a new color).
- Recursively or iteratively apply steps 2-3 to all neighboring cells.
- Continue until all connected cells meeting the criteria have been processed.
Implementing Flood Fill
Let’s implement Flood Fill using both recursive and iterative approaches in Python. We’ll use a 2D matrix as our example, where we’ll fill a connected region of the same value with a new value.
Recursive Approach
The recursive approach is often more intuitive and easier to understand. Here’s how we can implement it:
def flood_fill_recursive(matrix, x, y, old_color, new_color):
# Check if current cell is within the matrix and has the old color
if (x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0])
or matrix[x][y] != old_color):
return
# Fill the current cell
matrix[x][y] = new_color
# Recursively fill the neighboring cells
flood_fill_recursive(matrix, x+1, y, old_color, new_color) # Down
flood_fill_recursive(matrix, x-1, y, old_color, new_color) # Up
flood_fill_recursive(matrix, x, y+1, old_color, new_color) # Right
flood_fill_recursive(matrix, x, y-1, old_color, new_color) # Left
# Example usage
matrix = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
start_x, start_y = 2, 3 # Starting point
old_color = 0
new_color = 2
flood_fill_recursive(matrix, start_x, start_y, old_color, new_color)
for row in matrix:
print(row)In this recursive implementation, we start at the given cell (x, y) and check if it’s within the matrix bounds and has the old color. If so, we fill it with the new color and recursively call the function on its four neighboring cells.
Iterative Approach
While the recursive approach is elegant, it can lead to stack overflow for large matrices. The iterative approach using a queue or stack is more efficient for larger datasets:
from collections import deque
def flood_fill_iterative(matrix, x, y, old_color, new_color):
if matrix[x][y] != old_color:
return
queue = deque([(x, y)])
matrix[x][y] = new_color
while queue:
x, y = queue.popleft()
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
if (0 <= nx < len(matrix) and 0 <= ny < len(matrix[0])
and matrix[nx][ny] == old_color):
matrix[nx][ny] = new_color
queue.append((nx, ny))
# Example usage
matrix = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
start_x, start_y = 2, 3 # Starting point
old_color = 0
new_color = 2
flood_fill_iterative(matrix, start_x, start_y, old_color, new_color)
for row in matrix:
print(row)This iterative version uses a queue to keep track of cells to be processed. It’s more efficient for large matrices and avoids the risk of stack overflow.
Time and Space Complexity
Understanding the time and space complexity of Flood Fill is crucial for optimizing your solutions:
- Time Complexity: O(N), where N is the number of cells in the matrix. In the worst case, we might need to visit every cell in the matrix.
- Space Complexity:
- Recursive: O(N) in the worst case due to the call stack.
- Iterative: O(N) in the worst case if all cells are in the queue.
The iterative approach generally has better space complexity for large inputs due to avoiding potential stack overflow issues.
Common Variations and Extensions
As you prepare for coding interviews, it’s important to be aware of common variations of the Flood Fill problem:
1. 8-Directional Flood Fill
Instead of just considering 4 neighboring cells (up, down, left, right), you might need to consider all 8 directions including diagonals.
directions = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)
]
def flood_fill_8_directions(matrix, x, y, old_color, new_color):
if matrix[x][y] != old_color:
return
queue = deque([(x, y)])
matrix[x][y] = new_color
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (0 <= nx < len(matrix) and 0 <= ny < len(matrix[0])
and matrix[nx][ny] == old_color):
matrix[nx][ny] = new_color
queue.append((nx, ny))2. Boundary Flood Fill
Sometimes you might need to fill an area until you hit a boundary of a different color.
def boundary_flood_fill(matrix, x, y, new_color, boundary_color):
if matrix[x][y] == boundary_color or matrix[x][y] == new_color:
return
original_color = matrix[x][y]
queue = deque([(x, y)])
matrix[x][y] = new_color
while queue:
x, y = queue.popleft()
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
if (0 <= nx < len(matrix) and 0 <= ny < len(matrix[0])
and matrix[nx][ny] == original_color):
matrix[nx][ny] = new_color
queue.append((nx, ny))3. Multi-dimensional Flood Fill
While we’ve focused on 2D matrices, Flood Fill can be extended to 3D or even higher dimensions. The principle remains the same, but you’ll need to adjust the neighbor checking accordingly.
Real-world Problem: Image Segmentation
Let’s look at a practical application of Flood Fill in image segmentation. Imagine you have a black and white image represented as a 2D array, where 1 represents white and 0 represents black. You want to identify and label different connected components in the image.
def segment_image(image):
height, width = len(image), len(image[0])
label = 2 # Start labeling from 2 (0 and 1 are already used)
for i in range(height):
for j in range(width):
if image[i][j] == 1: # Found an unlabeled white pixel
flood_fill_iterative(image, i, j, 1, label)
label += 1
return image, label - 2 # Return segmented image and number of segments
# Example usage
image = [
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 1, 0, 0, 0]
]
segmented_image, num_segments = segment_image(image)
print(f"Number of segments: {num_segments}")
for row in segmented_image:
print(row)This code will identify and label each connected white region with a unique number, allowing you to count and analyze different segments in the image.
Interview Tips and Tricks
When tackling Flood Fill problems in coding interviews, keep these tips in mind:
- Clarify the Problem: Always ask about the dimensions of the matrix, the definition of connectivity (4-way or 8-way), and any specific constraints.
- Choose the Right Approach: Decide between recursive and iterative based on the problem size and constraints. If the matrix is large, prefer the iterative approach.
- Handle Edge Cases: Remember to check for matrix bounds and handle cases where the starting point is already the new color.
- Optimize Space: If asked, mention that you can optimize space by modifying the original matrix instead of creating a new one.
- Consider Variations: Be prepared to modify your solution for different connectivity rules or multi-dimensional arrays.
- Think About Applications: Discussing real-world applications of Flood Fill can impress your interviewer and demonstrate broader understanding.
Practice Problems
To solidify your understanding of Flood Fill, try these practice problems:
- LeetCode 733. Flood Fill: A straightforward implementation of the basic Flood Fill algorithm.
- LeetCode 200. Number of Islands: Uses Flood Fill to count connected components.
- LeetCode 1091. Shortest Path in Binary Matrix: Combines Flood Fill with shortest path finding.
- LeetCode 994. Rotting Oranges: A multi-source Flood Fill problem.
- LeetCode 130. Surrounded Regions: A boundary-based Flood Fill variation.
Conclusion
Mastering the Flood Fill algorithm is a significant step in your journey to becoming a proficient programmer. Its applications span various domains, from image processing to game development, making it a valuable tool in your coding arsenal. As you practice, remember that the key to excelling in coding interviews is not just knowing the algorithm, but understanding its nuances and being able to adapt it to different scenarios.
At AlgoCademy, we believe in equipping you with both the theoretical knowledge and practical skills needed to tackle complex programming challenges. Flood Fill is just one of the many algorithms and techniques we cover in our comprehensive curriculum designed to prepare you for technical interviews at top tech companies.
Keep practicing, exploring variations, and most importantly, thinking about how these algorithms can be applied to solve real-world problems. With dedication and the right resources, you’ll be well on your way to acing your coding interviews and building a successful career in software development.
Happy coding, and may your skills continue to flood the tech world with innovation!