# Most efficent way of finding submatrices of a matrix

- contain at least L ones and L zeros
- contain max H elements

- H=5 -> divisors [1 5] -> possibile rectangles of area 5 are 1x5 and 5x1
- 4 -> divisors [1 2 4] -> possibile rectangles of area 4 are 1x4 4x1 and 2x2
- 3 -> divisors [1 3] -> possibile rectangles of area 3 are 3x1 and 1x3
- 2*L=2 -> divisors [1 2] -> possibile rectangles of area 2 are 2x1 and 1x2

##### 2 Comments

### Accepted Answer

Might I suggest you are doing this the wrong way? And fairly massively so?

A = [ 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1];

If you want to find all 2x2 submatrices of A that have at least 1 zero and at least one 1, then consider the following matrix, computed from A:

cA = conv2(A,ones(2,2),'valid') cA = 3 4 4 2 1 2 2 3 3 1 2 3 1 3 2 1 3 3 1 2 1 1 2 3 0 0 0 0 0 2

So the upper left corner of all such 2x2 matrices resides at the following locations:

[i,j] = find((cA >= 0) & (cA < 4)); [i,j] ans = 1 1 2 1 3 1 4 1 5 1 2 2 3 2 4 2 5 2 2 3 3 3 4 3 5 3 1 4 2 4 3 4 4 4 5 4 1 5 2 5 3 5 4 5 5 5 1 6 2 6 3 6 4 6 5 6

The other corner of those matrices is pretty easy to find now, since you know they are 2x2 sub-matrices.

The point is, even for a relatively large matrix A (I would not even consider 200x200 even remotely large here) the above computation would be trivial, and almost immediate. For example:

A = double(rand(200,200) < 0.5); timeit(@() conv2(A,ones(2,2),'valid')) ans = 0.00021959

The find will be also trivially fast. But the point is, a large amount of the code you painstakingly wrote above could be replaced by two efficient lines.

##### 1 Comment

### More Answers (0)

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!