Solving maximum connected cell problem using Connected Component in Graph(DFS) and Cell grid representation in Java

A problem among varieties of coding tests that fascinated me to find the solution after I could not complete it on time is “maximum connected cell”. Let have some cell values as below and the number 1 is considered as eligible cell and it connect to neighbored cells when they have the same value.

Sample maximum connected cell problem. Yellow is the solution to find.

We have 5x5 grid which contain 25 cells and the green and yellow highlight are the eligible connected cell. The answer is yellow highlight because it has size 11 which is longest than the green one.

Therefore, how to find such a solution ?. It keep remaining in my mind util I recall one Algorithm called Depth First Search in Graph and some key feature called Connected Component (CC). I decide to re-read this algorithm again and yes it solves the above problem by using Graph ADT representation.

1. CC and Graph ADT , solution to above problem

What is a Graph ( Undirected graph )?

Graph is is a set of vertices and a collection of edges that each connect a pair of vertices.

There is a function to find a set of connected vertex from one to another which is can be solved using DFS ( Depth first search) called Connected Component.

So the only key for us now is to transform above grid to Graph.

In Graph we talk about vertex and edge . So below is the transformation, high light is the connected vertex :

Graph representation for connected cells

To solve problem with Connected component we need Graph ADT and Connected component (CC) class. I create the Graph and CC class following sample from the book “Algorithms” by “Robert Sedgewick and Kevin Wayne” ( but I use Set , existing Collection Framework instead of Bag ) .

Inside , ConnectedComponent class I utilize the DFS ( Depth First Search ) by adding one private method called addVertex for tracking the length of connected vertex and return it for compare it later.

So after that we can use the combination of Graph and CC by transforming our Grid cell into Graph . I used 2D array to present above cell& grid . It’s required function to convert cell location ( i, j) to vertex and vice versa for easy processing. Below is the full code of transformation and experiment:

Here is the result of applied Graph solution :

Result of Max connected cell using CC (DFS) Graph Representation

2. Introduction to cell representative class to solve same problem

There is another solution which not depend on Graph processing but based on referencing a set of Cells as tree like and adding it at the run time.

This can be separated into below categories :

1.Create a cell class representation and collection object of connected cell ( like a tree ) inside the cell class itself

2. Creating Grid class representation by replicate the rectangle of 2D array of connected cell and traversing through that 2D array for each element to :

a. Create new cell object and put it inside another 2D array of cell which encapsulated inside that grid.

b. Look for neighbor cells during creation and if the neighbored cell contain already a set of connected cell we just add current cell to that collection . Otherwise creating new set and reference it inside the current cell.

Below are the codes for Cell and Grid class.

So we can create Test Client class like we did in Graph in section 1 .

And here is the output which produces the same result:

Grid, Cell class solving maximum connected cell problem

Comparison and conclusion

The above problem can be transformed to any issues representative depend on the creativity of the questioner. We can either use Graph ADT or Cell ,Grid class to solve that problem . Let analyse both solutions.

Connected component on Graph ADT:

Time complexity is propositional to : E + V = number of edge and vertex

Space complexity is propositional to : E + V + number connected vertex paths

In this case number of Vertex is equal to the number of cells while edge is equal to the connected cells.

Cell grid class representative ADT :

Time complexity is propositional to : connected neighbored cells * n + (O) adding cell to connected cell

Adding connected set which propositional to 1

Connected neighbored cells can be up to 4, so Time complexity can be updated as below:

4*n => n ( number of cells )

Space complexity is propositional to : n ( number of cells )+ number connected sets or paths

Since it duplicate the 2D array of integer to be 2D array of cells and store the connected cells inside every cell similar to the tree.

In conclusion ,Cell grid class is consuming a bit less space and a bit less time than CC Graph ADT but it’s tricky to implement. Without proper referencing it’s hard to achieve the expected result while CC is elegant and easy to understand as well as implement based on simple modern data structure .

That’s all ,please refer to here https://github.com/engleangs/ConnectedCells for full source code of the problem. For detail explanations of Graph and other creative problems I recommend to read this book “ Algorithm 4th edition “ by “ Robert Sedgewick and Kevin Wayne”.