Maximum connected cell length containing two different numbers

Question

Suppose we are given an $n\times m$ matrix $M$ of positive integers. The adjacent cells of a particular cell is the up, down, left and right cells. Like for cell $M[i][j]$ the adjacent cells are $M[i-1][j]$, $M[i+1][j]$, $M[i][j-1]$ and $M[i][j+1]$ respectively.

An area is a set of cells such that for each pair of cells $(u_0,v)$ in the area, there is a sequence of cells $u_1,\ldots,u_k$ in the area such that $u_{i+1}$ is an adjacent cell of $u_i$ and $u_k$ is an adjacent cell of $v$. The problem is to find out a maximum area (i.e. an area with maximum number of cells) of this matrix which contains exactly two different numbers.

For an example: $$M=\begin{bmatrix}5&3&2&5&5\\2&1&2&5&3\\6&1&5&2&5\\5&2&5&3&5\\4&6&8&9&6\end{bmatrix},$$ Here the maximum area contains 10 cells. And the area is: $$\begin{bmatrix}*&*&2&5&5\\*&*&2&5&*\\*&*&5&2&*\\5&2&5&*&*\\*&*&*&*&*\end{bmatrix}.$$ What is the most efficient way to find the maximum area?

Answer 1

First you can transform the matrix to a graph, where every maximal area containing the same integer is transformed to a vertex with a weight that is the number of cells in the area, and there is an edge between two vertices iff the two corresponding areas are adjacent, that is, there is a cell in one area that is adjacent to at least one cell in the other area. Therefore, the matrix in your example is transformed to

5 - 3 - 2 - 5
|   | / |   | \
2 - 1   |   |   3
| / | \ |   |   |
6   |   5 - 2 - 5
|   | / | \ | / |
5 - 2   |   3   |
|   |   |   |   |
4 - 6 - 8 - 9 - 6

Now the problem turns out to be finding the connected subgraph with maximum sum of weights such that it contains exactly two integers. This transformation can be done in $O(mn)$ time.

Next, run the following algorithm:

maxS := empty set
While True:
    Search the next edge (u,v) that is not used
    If not found:
        return maxS
    Let x,y be the integers contained in u,v respectively
    (#) Do BFS from u where only edges between vertices containing x,y respectively are considered
    Mark all edges found during the BFS as used
    S := the set of vertices found during the BFS
    If the sum of weights in S > the sum of weights in maxS
        maxS := S

Note the (#) line, this algorithm requires us to, given a vertex containing integer x, efficiently find all its neighbors (as well as edges) containing y. You can sort all the neighbors for all vertices in advance, which takes $O(\sum_v n_v\log n_v)=O(mn\log(mn))$ time ($n_v$ is the number of neighbors of vertex $v$). Now compared to normal BFS, it takes extra $O(\log n_v)$ time for each vertex $v$.

Basically, each BFS induces a maximal connected subgraph containing exactly two integers. This algorithm checks all such subgraphs and choose the optimal one. Note each edge belongs to only one such subgraph and each vertex $v$ belongs to $t_v$ such subgraphs ($t_v$ is the number of distinct integers among all neighbors of $v$), the time complexity of this algorithm is

$$O\left(mn+\sum_vt_v\log n_v\right)=O\left(mn\log(mn)\right).$$