CODEWITHSUNDEEP
algorithmmatrix
supercheetah
supercheetah

Reputation: 3250

How can I find all contiguous submatrices?

I'm just having a hard time figuring this out. I promise it's not for homework.

Given a matrix of arbitrary size like the following (with (0, 0) being in the upper left corner):

1 0 0 1 0 0
0 0 1 1 1 0
0 1 1 1 0 0
0 1 1 1 0 0
0 1 0 1 0 0

I've been trying to figure out how to find the coordinates of all the contiguous submatrices with ones in them. In this example, I should get a list like this: 

[(2, 1), (3, 3)
 (1, 2), (3, 3)]

I'm having a hard time figuring out how to come up with a list like this. I know the algorithm isn't going to be efficient (I'm guessing O(n^2)), and that's fine because the matrices I'll be working with aren't going to be that big.

Even just giving me a clue on figuring this out would be greatly appreciated.

Upvotes: 0

Views: 721

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70939

Best solution you can have is O(N^4) as this is the maximum size of answer you can have(in case all values are ones).

To write a O(N^4) solution do the following - use an helper array of size O(N^2) and in each of its cells store the number of ones in in the submatrix with upper left corner in (0,0) and lower right corner in the given cell. Having this array you can compute the number of ones in the matrix (a,b)(upper left) -> (c,d)(lower right) constantly using:

num_of_ones(a,b,c,d) = helper_matrix[c][d] + helper_matrix[a-1][b-1] -helper_matrix[a-1][d] -helper_matrix[c][b-1].

Take care of the cases when a-1 or b-1 falls out of the array.

Using the above check if each submatrix is only filled with ones(i.e. the number of ones in it is equal to the size of the submatrix).

Upvotes: 1

Related Questions