Find biggest pattern in a given matrix

Question

I am new to the world of algorithmic problems and this one has been giving me hard time. I have been trying to solve this for a few days and at this point I feel kinda lost. I have a solution but it is way too slow for huge inputs, so I am currently trying to find somewhat more efficient way.

The goal is to find the biggest SIZE (output is the number) of pattern in the shape of H in a given matrix that consists of dots ('.'), circles ('o') and X letters ('X'). The matrix has m rows and n columns. 2 ≤ m, n ≤ 2000.

The pattern must be composed of dots('.') and may contain only one circle ('o') at most. The pattern must not contain any 'X' letters. The pattern is composed of left, right and middle pillar and the middle pillar cannot touch the the top or the bottom of left or right pillar.

e.g.:

X...
.o..
X...
..o.

In the matrix above the biggest size of H is 9.

This patterns are allowed:

. .     .       .                                              
. o     .       .
. .     .........
. .     .       .    . .
...     .       .    ...
. .     .       .    . .

but these variants are not allowed:

.    o 
.    .
.    .
.    .
......            

.....o 
.    .
.    .
.    .
.    .

The ways I have been thinking about this:

My naive solution looked like this:

 for (int leftCol = 0; leftCol < n - 2; leftCol ++ ){
 for (int rightCol = n-1; rightCol > leftCol + 1; rightCol--){
  //searchForBiggestHLeftO() with 'o' in the "left pillar" of H between rightCol and leftCol
  //searchForBiggestHRightO() with 'o' in the "right pillar" of H between rightCol and leftCol
  //searchForBiggestHMiddleO() with 'o' in the "middle pillar" of H between rightCol and leftCol
  //searchForBiggestH() without any 'o' between rightCol and leftCol

 }  
}

The solution above (even though it worked) became useless for matrices of bigger size (hundreds x hundreds or even thousands x thousands). Since that I have been trying to find other more efficient ways to compute the size of H.

The most similar problem I found on the internet was the solution on how to find the biggest pattern of shape '+' composed of '1' in a binary matrix.

https://www.geeksforgeeks.org/find-size-of-the-largest-formed-by-all-ones-in-a-binary-matrix/

But unfortunately I have not been able to apply the solving algorithms in any functioning way. The fact that the patter may contain one circle 'o' became my stumbling point.

I believe there is some handy way of how to view this problem that I have failed to see. Thanks for your time.

user_2144669 · Answer

In O(m n) time, we can compute for each matrix entry

How many consecutive dots are above (below, left of, right of) it
How many consecutive entries above (below, left of, right of) it are neither X nor a second circle

by scanning each column upward and downward and each row leftward and rightward. This leads to an O(m n²)-time algorithm by iterating over rows, iterating over pairs of entries in the row (i.e., guessing the degree-3 vertices of the H), doing constant work on the computations above.

Actually I think we can do better. Sketchy details here, but guess the row (i.e., iterate over rows), sort the columns by how high they can reach with and without including a circle, and insert them in decreasing order of height into an online data structure with operations

Insert(i, depth)
Query(i′, depth′): returns the maximum value of |i − i′| + min(depth, depth′) for previously inserted (i, depth),

implemented using an appropriately augmented segment tree.

Find biggest pattern in a given matrix

1 Answers