Flood Fill Image Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/flood-fill-image

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an image as a matrix of colored cells. Each cell has a value ranging from 0 to 65535 denoting its color. You have to apply flood-fill to a particular cell of the matrix with color c. Two cells are considered as part of the same connected component if they have a common side and the same color value. When you apply flood-fill to a particular cell, all its connected components are also applied the same color. Return the resultant matrix.

Approach

The approach to solving this problem is based on an algorithm called Flood Fill Algorithm, which is basically a DFS on Grid algorithm. We use a recursive DFS to try to move in all the valid directions from our current cell and reach all the cells in that connected component as the given cell. Whenever, we can reach a required cell, we can colour it in the given colour in place, and finally return the resultant matrix.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Implementation

C++

void floodFill(vector<vector<int>> &image, vector<vector<int>> visited, int x, int y, int c, int initialColour) {
	if(x < 0 || y < 0 || x >= image.size() || y >= image[0].size()) {
		return;
	}
	if(visited[x][y] == 1 || image[x][y] != initialColour) {
		return;
	}
	visited[x][y] = 1;
	image[x][y] = c;
	floodFill(image, visited, x - 1, y, c, initialColour);
	floodFill(image, visited, x, y - 1, c, initialColour);
	floodFill(image, visited, x, y + 1, c, initialColour);
	floodFill(image, visited, x + 1, y, c, initialColour);
}
vector<vector<int> > applyFloodFill(vector<vector<int> > image, int x, int y, int c){
	vector<vector<int>> visited(image.size(), vector<int> (image[0].size(), 0));
    floodFill(image, visited, x, y, c, image[x][y]);
	return image;
}

Java

class Solution {
	void floodFill(int[][] image, int[][] visited, int x, int y, int c, int initialColour) {
		if(x < 0 || y < 0 || x >= image.length || y >= image[0].length) {
			return;
		}
		if(visited[x][y] == 1 || image[x][y] != initialColour) {
			return;
		}
		visited[x][y] = 1;
		image[x][y] = c;
		floodFill(image, visited, x - 1, y, c, initialColour);
		floodFill(image, visited, x,  y - 1, c, initialColour);
		floodFill(image, visited, x, y + 1, c, initialColour);
		floodFill(image, visited, x + 1, y, c, initialColour);
	}
	int[][] applyFloodFill(int[][] image, int x, int y, int c){
		int visited[][] = new int[image.length][image[0].length];
	    floodFill(image, visited, x, y, c, image[x][y]);
		return image;
	}
}