Solving Connected Cells [DFS Algorithm] | Python | HackerRank Solution | Binary Matrix Boundary

#dfs #hackerrank #binarymatrix

Link to the HackerRank problem statement:

The graphical explanation for the binary matrix connecte cell problem. Using the DFS algorithm in python language.

Closed Captioning:
Consider a binary matrix like this.
We have each cell of the matrix filled with either 0 or 1.
We will be writing a program to find the maximum number of connected cells having value 1 in the matrix.
Here, we have 4 regions in the matrix containing value 1.
Out of the 4 regions, this region has 7 connected cells having value 1, which is the maximum number of connected cells in this matrix.

In our program, first we will set a maximum cell counter with initial value 0.
Then we will start iterating through each cell of the matrix.
When we find a cell with value 1, we will consider it as a new region and set the region cell count to 1.
After taking the count, to mark the cell as visited, we will change it's value from 1 to 0.
After that,we will check whether any of it's neighbor is having value 1.

If no neighbors are found, we will check whether the current region cell count is greater than the maximum cell counter.
If yes, a new maximum cell count is set.

If neighbor cells are having value 1, we will continue this operation for the neighboring cells too.

We will continue with the iteration in this manner.
After iterating through all the cells, the value of maximum cell counter will be displayed as the answer.

This program can be classified under Depth First Search Algorithm.

Let's open the code editor in full screen mode.
Change the language to Python 3.
There is already some code provided in the editor.
We just have to complete this function.
As an argument to the function, we do have the input matrix here named 'grid'.

Let's start coding.
First, we will initialize a variable 'max_cell_counter' with value 0.
Now, we will add two 'for' loops to iterate through the list 'grid'.
In python, a matrix will be represented as a list which contains lists as its elements.
In this case, our matrix 'grid' is a list which contains each row of the matrix as its element.
To get the number of rows, we will check the length of 'grid'.
To get the number of columns, we will check the length of the first element of 'grid'.
While iterating through each cell, we will check whether the current cell contains the value 1.
If yes, we will calculate the number of cells having value 1, including its neighbor.
For this purpose, we will write a separate function 'count_region_cells'.
This function will take the grid, current row and current column as the arguments.
And this function will return the total region cell count.
The result will be stored in a variable 'region_cell_count'.
At this point, we will check whether the current region cell count is greater than the existing maximum cell count.
That is, the maximum value among the current region cell count and existing maximum cell count will be the new maximum value.
This value will be returned as the result to the main function.

Now let's write the definition for the function 'count_region_cells'.
First will set the cell count as 1.
This variable will be returned from this function.
Now, to mark the current cell as visited, let's set the value of current cell as 0.
We also need to check whether there are any neighboring cells with value 1.
For that, let's write two 'for' loops to iterate through the neighboring cells.
For this sub matrix, the row will start with the previous row of grid, and row will end with next row of grid.
That is row-1 and row+2 will be passed as the arguments to the range of row loop statement.
Similarly, col-1 and col+2 will be passed as the arguments to the range of column loop statement.
Notice that the range functions second argument is not inclusive.
While iterating, for loop may process the current cell again.
To avoid that, we put the condition that either the sub matrix row is not equal to the parent matrix row, or sub matrix column not equal to the parent matrix column.
For each iteration, we will be checking and counting the neighboring cells one after the other till there are no more connected cell, for which this function will be called recursively.
That is, this function will be calling itself again and again.

Now the only missing piece here is the exit condition for our function.
While processing a cell, one condition for exit can be, the cell is outside the boundary.
The checks can be row less than first row, column less than first column, row greater than last row, or column greater than last column.
If any of this scenario happens, return the cell count as 0.

Also, another condition for exit will be the value of the cell is 0.
In that case too, return the cell count as 0.

[anjaliagrawal]

Thank you so much for this. Please keep posting similar videos.

[vinayakmittal]

your explanation is much clear than other channels on youtube
please keep posting videos like this
thank you

[josejayant]

I tried your algorithm in c++. I was having problem with the cell_count variable but i was able to fix it but then i learned there is one more problem the loop doesn't exit once all the 1's are visited and changed to 0 . What to do now?

[ngocloile]

thank you bro! really clear and easy to understand.

[DIZt]

what is the big-o of this algorithme ?

[kumarr]

I tried your code but got the error : for r in range(row-1, row+2):
RecursionError: maximum recursion depth exceeded in comparison

help me fix this error
thanks for the explanation it was really digestible