Solution Approach
Solution Overview
There are 2 main approaches to solve this problem:
- Recursive DFS Approach - Complex approach
- Iterative BFS Approach - Complex approach
Approach 1: Recursive DFS Approach
The recursive Depth-First Search (DFS) approach is a natural fit for the flood fill algorithm. Starting from the given pixel, we recursively explore all adjacent pixels of the same color, changing them to the new color as we go.
This approach is intuitive because it directly models how the paint would "flow" from the starting pixel to all connected pixels of the same color.
Algorithm:
- Define a recursive function floodFill(canvas, row, col, originalColor, newColor) that takes the canvas, current position, original color, and new color as parameters.
- Base cases: If the current position is out of bounds, or the current pixel is not the original color, or it's already the new color, return without doing anything.
- Set the current pixel to the new color.
- Recursively call floodFill on all four adjacent pixels (up, down, left, right).
- The main function should initialize originalColor to the color of the starting pixel and then call the recursive function.
Time Complexity:
In the worst case, we might need to visit all pixels in the canvas once, where m is the number of rows and n is the number of columns.
Space Complexity:
The recursion stack can grow up to the size of the canvas in the worst case (e.g., if the entire canvas is filled with the same color).
Approach 2: Iterative BFS Approach
An alternative approach is to use Breadth-First Search (BFS) with a queue. This approach processes pixels level by level, starting from the given pixel and expanding outward.
While this approach is less intuitive than the recursive DFS, it has the advantage of avoiding potential stack overflow for very large canvases.
Algorithm:
- Initialize a queue with the starting pixel.
- Get the original color from the starting pixel.
- While the queue is not empty:
- - Dequeue a pixel.
- - If the pixel is out of bounds, or not the original color, or already the new color, skip it.
- - Set the pixel to the new color.
- - Enqueue all four adjacent pixels (up, down, left, right).
Time Complexity:
Similar to the recursive approach, we might need to visit all pixels in the canvas once.
Space Complexity:
The queue will contain at most min(m, n) elements at any time, which is the maximum number of pixels in a level of the BFS traversal.
Pseudocode
1234567891011121314151617181920212223242526272829function floodFill(canvas, startRow, startCol, newColor): originalColor = canvas[startRow][startCol] // If the starting pixel is already the new color, no need to do anything if originalColor == newColor: return canvas // Call the recursive helper function dfs(canvas, startRow, startCol, originalColor, newColor) return canvas function dfs(canvas, row, col, originalColor, newColor): // Check if the current position is valid if row < 0 or row >= canvas.length or col < 0 or col >= canvas[0].length: return // Check if the current pixel is the original color if canvas[row][col] != originalColor: return // Change the color of the current pixel canvas[row][col] = newColor // Recursively fill the adjacent pixels dfs(canvas, row + 1, col, originalColor, newColor) // Down dfs(canvas, row - 1, col, originalColor, newColor) // Up dfs(canvas, row, col + 1, originalColor, newColor) // Right dfs(canvas, row, col - 1, originalColor, newColor) // LeftString Problems
Learning Objective
Understand different approaches to solve the digital paint bucket tool problem and analyze their efficiency.
Solution Approaches
Approach 1: Recursive DFS Approach
The recursive Depth-First Search (DFS) approach is a natural fit for the flood fill algorithm. Starting from the given pixel, we recursively explore all adjacent pixels of the same color, changing them to the new color as we go.
This approach is intuitive because it directly models how the paint would "flow" from the starting pixel to all connected pixels of the same color.
Algorithm:
- Define a recursive function floodFill(canvas, row, col, originalColor, newColor) that takes the canvas, current position, original color, and new color as parameters.
- Base cases: If the current position is out of bounds, or the current pixel is not the original color, or it's already the new color, return without doing anything.
- Set the current pixel to the new color.
- Recursively call floodFill on all four adjacent pixels (up, down, left, right).
- The main function should initialize originalColor to the color of the starting pixel and then call the recursive function.
Approach 2: Iterative BFS Approach
An alternative approach is to use Breadth-First Search (BFS) with a queue. This approach processes pixels level by level, starting from the given pixel and expanding outward.
While this approach is less intuitive than the recursive DFS, it has the advantage of avoiding potential stack overflow for very large canvases.
Algorithm:
- Initialize a queue with the starting pixel.
- Get the original color from the starting pixel.
- While the queue is not empty:
- - Dequeue a pixel.
- - If the pixel is out of bounds, or not the original color, or already the new color, skip it.
- - Set the pixel to the new color.
- - Enqueue all four adjacent pixels (up, down, left, right).
Complexity Analysis
Recursive DFS Approach Approach
Time Complexity
In the worst case, we might need to visit all pixels in the canvas once, where m is the number of rows and n is the number of columns.
Space Complexity
The recursion stack can grow up to the size of the canvas in the worst case (e.g., if the entire canvas is filled with the same color).
Iterative BFS Approach Approach
Time Complexity
Similar to the recursive approach, we might need to visit all pixels in the canvas once.
Space Complexity
The queue will contain at most min(m, n) elements at any time, which is the maximum number of pixels in a level of the BFS traversal.
Comparison:
Both the recursive DFS and iterative BFS approaches have the same time complexity of O(m × n), but they differ in space complexity and practical considerations. The recursive DFS approach is more intuitive and easier to implement, but it can lead to stack overflow for very large canvases. The iterative BFS approach uses less space in the worst case and avoids stack overflow, but it's slightly more complex to implement. In practice, for most digital art applications with reasonably sized canvases, the recursive DFS approach is perfectly adequate and more natural to understand.
Pseudocode
Recursive DFS Approach Approach
1234567891011121314151617181920212223242526272829function floodFill(canvas, startRow, startCol, newColor): originalColor = canvas[startRow][startCol] // If the starting pixel is already the new color, no need to do anything if originalColor == newColor: return canvas // Call the recursive helper function dfs(canvas, startRow, startCol, originalColor, newColor) return canvas function dfs(canvas, row, col, originalColor, newColor): // Check if the current position is valid if row < 0 or row >= canvas.length or col < 0 or col >= canvas[0].length: return // Check if the current pixel is the original color if canvas[row][col] != originalColor: return // Change the color of the current pixel canvas[row][col] = newColor // Recursively fill the adjacent pixels dfs(canvas, row + 1, col, originalColor, newColor) // Down dfs(canvas, row - 1, col, originalColor, newColor) // Up dfs(canvas, row, col + 1, originalColor, newColor) // Right dfs(canvas, row, col - 1, originalColor, newColor) // LeftIterative BFS Approach Approach
1234567891011121314151617181920212223242526272829303132function floodFill(canvas, startRow, startCol, newColor): originalColor = canvas[startRow][startCol] // If the starting pixel is already the new color, no need to do anything if originalColor == newColor: return canvas // Initialize a queue with the starting pixel queue = new Queue() queue.enqueue([startRow, startCol]) while not queue.isEmpty(): [row, col] = queue.dequeue() // Check if the current position is valid if row < 0 or row >= canvas.length or col < 0 or col >= canvas[0].length: continue // Check if the current pixel is the original color if canvas[row][col] != originalColor: continue // Change the color of the current pixel canvas[row][col] = newColor // Enqueue the adjacent pixels queue.enqueue([row + 1, col]) // Down queue.enqueue([row - 1, col]) // Up queue.enqueue([row, col + 1]) // Right queue.enqueue([row, col - 1]) // Left return canvas