Difficulty: Medium, Asked-In: Amazon, Microsoft
Key takeaway: An excellent problem to learn problem-solving using iterative (BFS) and recursive (DFS) approaches.
The flood fill problem is a way to fill a region of connected pixels with a new colour, starting from a given pixel in an image. Here an image is represented by a grid of pixels and each pixel is represented by an integer value.
You are given an image represented by an m x n grid of integers, where image[i][j] represents the pixel value at position (i, j). You are also given the coordinates of a starting pixel (x, y) and a new color to use for the flood fill operation.
The goal is to replace the color of all pixels connected to the starting pixel in the four cardinal directions (up, down, left, right) with the new color, as well as any pixels connected to those pixels, and so on. Once the flood fill is complete, you should return the modified image.
One idea is to explore all the regions connected to a given color and paint them with a new color. To do this, we begin at a specified starting point (x, y) and paint it with the new color. We then check the surrounding points (x, y + 1), (x - 1, y), (x + 1, y), and (x, y - 1) to ensure that they are valid and have the same color as the original. If they do, we also paint them with the new color and repeat this process recursively for their surrounding points. This continues until all the connected points of the original color have been painted with the new color.
We define a function called floodFill that takes an image, a starting point (x, y), and a new colour to be filled. Inside the function, we first check if the starting point already has the same colour as the new colour. If it does, there is no need to perform the flood fill. Otherwise, we call the floodFillHelper function to fill the connected region with the new colour. FloodFillHelper is a recursive function that takes an image, a current point (x, y), the original colour, and the new colour.
Inside floodFillHelper, we check if the current point (x, y) has the same colour as the original colour. If it does, we change the colour of the current point to the new colour, and call the function recursively on the four neighbouring points: (x, y + 1), (x - 1, y), (x + 1, y), and (x, y - 1). We also ensure that these points are within the bounds of the image and have the same colour as the original.
This process continues until all connected points with the original color have been colored with the new color.
void floodFillHelper(std::vector<std::vector<int>>& image, int x, int y, int color, int newColor)
{
int m = image.size();
int n = image[0].size();
if (image[x][y] == color)
{
image[x][y] = newColor;
if (x >= 1)
floodFillHelper(image, x - 1, y, color, newColor);
if (y >= 1)
floodFillHelper(image, x, y - 1, color, newColor);
if (x + 1 < m)
floodFillHelper(image, x + 1, y, color, newColor);
if (y + 1 < n)
floodFillHelper(image, x, y + 1, color, newColor);
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int x, int y, int newColor)
{
int color = image[x][y];
if (color != newColor)
floodFillHelper(image, x, y, color, newColor);
return image;
}
The time complexity of this code is O(m*n), where m and n are the dimensions of the image. This is because the worst-case time complexity occurs when we need to visit and update every pixel in the image.
The space complexity of this code is O(m*n). This is because in the worst case, the recursion stack will maintain a frame for every pixel in the image.
The flood fill algorithm using DFS, as shown above, is tail recursive. This means that the recursive calls are the last instruction in the algorithm, thus it can be easily implemented iteratively by using the stack data structure.
To begin, we push the starting point (x, y) onto the stack. Then, we run a loop until the stack is empty. In each iteration of the loop, we pop a point from the stack. If the point has the same color as the starting point (x, y), we color it with the new color, and push any surrounding points onto the stack. By the end of this process, all points in the connected region will have been colored.
vector<vector<int>> floodFill(vector<vector<int>>& image,
int x, int y, int newColor)
{
if (image[x][y] == newColor)
return image;
int m = image.size();
int n = image[0].size();
int temp = image[x][y];
stack<pair<int, int>> stack;
stack.push({x, y});
while (stack.empty() == false)
{
int i = stack.top().first,
int j = stack.top().second;
stack.pop();
if (image[i][j] == temp)
{
image[i][j] = newColor;
if (i + 1 < m)
stack.push({i + 1, j});
if (i - 1 >= 0)
stack.push({i - 1, j});
if (j + 1 < n)
stack.push({i, j + 1});
if (j - 1 >= 0)
stack.push({i, j - 1});
}
}
return image;
}
The time complexity of this implementation is O(mn) in the worst case because, in the worst case, we need to visit each point in the image at most once. Similarly, the space complexity is also O(mn) in the worst case, as we need to store all m * n points on the stack in the worst case.
Just like DFS traversal, the breadth-first search (BFS) algorithm can also be used to visit points in the image and color the connected region of points starting from (x, y). To accomplish this, we initialize a queue to hold the points that need to be visited and push the starting point into it. Before entering the loop, we also save the original color of the starting point in a variable.
Now, we run a loop for BFS traversal where we continuously pop points from the front of the queue and color them with the new color. For each point, we also push the four neighboring points (top, bottom, left, and right) into the queue if they are within the bounds of the image and have the same color as the original. This process continues until the queue is empty.
The floodFill() function takes four parameters: a reference to a 2D matrix of integers representing the image, the row and column indices of the starting pixel (x, y), and the newColor.
We also store the original color of the starting pixel in the variable orginalColor and define a vector of integers called offsets {-1, 0, 1, 0, -1} which will be used to traverse the image in the four cardinal directions. All surrounding points of point (x, y) are:
Now, we run a loop until the queue is empty.
vector<vector<int>> floodFill(vector<vector<int>>& image, int x, int y, int newColor)
{
if (image[x][y] == newColor)
return image;
int m = image.size(),
int n = image[0].size();
queue<pair<int, int>> q;
q.push(make_pair(x, y));
int orginalColor = image[x][y];
vector<int> offsets = {-1, 0, 1, 0, -1};
while(q.size())
{
pair<int, int> p = q.front();
q.pop();
image[p.first][p.second] = newColor;
for (int i = 0; i < offsets.size() - 1; i = i + 1)
{
if(p.first + offsets[i] >= 0 // within upper bound
&& p.first + offsets[i] < m // within lower bound
&& p.second + offsets[i + 1] >= 0 // within left bound
&& p.second + offsets[i + 1] < n // within right bound
&& image[p.first + offsets[i]][p.second + offsets[i + 1]] == orginalColor)
{
q.push(make_pair(p.first + offsets[i], p.second + offsets[i+1]));
}
}
}
return image;
}
The time complexity of this implementation is O(mn) in the worst case because, in the worst case, BFS traversal needs to visit each point in the image at most once. Similarly, the space complexity is also O(mn) in the worst case, as we need to store all m * n points on the queue in the worst case.
The Flood Fill algorithm is used in many areas of computer science, including image processing, computer graphics, and game development.
One of the main advantages of the Flood Fill algorithm is its simplicity and speed. It can be implemented in just a few lines of code and can quickly fill large areas of an image or game environment. However, the algorithm can be affected by memory limits or the large number of connected areas, and performance may become an issue.
Number of Islands: Given a 2D grid of 1s and 0s, where 1 represents land and 0 represents water, count the number of islands in the grid. An island is a group of connected 1s, where a connection is defined as being adjacent horizontally or vertically (not diagonally).
Surrounded Regions: Given a 2D grid of characters, where 'X' represents an obstacle and 'O' represents an open space, identify all the regions that are surrounded by 'X' characters and replace them with 'X'. A region is considered surrounded if it is not connected to any open space on the grid.
Knight's Shortest Path: You are given a chessboard and a starting position for a knight piece. Your task is to find the shortest path for the knight to reach a given destination on the chessboard. The knight moves in an L-shaped pattern, two spaces horizontally and one space vertically, or two spaces vertically and one space horizontally.
Shortest Distance in a Grid with Obstacles: You are given a 2D grid of integers, where some cells contain obstacles and cannot be passed through. Your task is to find the shortest distance between two points in the grid.
Unique Paths: You are given a 2D grid of integers, where 1 represents a block that you cannot pass through and 0 represents an open space that you can pass through. Your task is to count the number of unique paths from the top-left corner to the bottom-right corner of the grid.
Maze: You are given a 2D grid of characters, where 'S' represents the start point, 'E' represents the end point, and '#' represents a wall that you cannot pass through. Your task is to find a path through the maze from the start point to the end point.
Enjoy learning, enjoy coding, enjoy algorithms!