Count the number of positions in a matrix which form a rectangle

I have a square matrix which contains only 0's and 1's. For example,

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

I would like to count the number of rectangles which have 1's as their vertices and which edges are parallel to rows and columns of the matrix. It is allowed to have 0's on the rectangle's edge. Here is an example of such a rectangle (its vertices are in square brackets)

[1]  0  1  1  [1]
 1   1  0  0   1
 1   0  1  1   0
 0   1  1  1   1
[1]  0  1  1  [1]

I have looked into link1 and link2 but still have no clue..

In the worst case the matrix has no zeroes and thus it can have O(𝑛²) top-left corners combined with as many bottom-right corners, making for O(𝑛⁴) rectangles.

So if you would have to output each rectangle, the time complexity would be O(𝑛⁴). But as you only need to count the rectangles and not produce the rectangles themselves, you can save some time and do it with a time complexity of O(𝑛³).

The idea is to select every possible pair of rows, and then count how many columns have a 1 in both selected rows. Each combination of 2x2 should be accounted for. This is a triangular number: if the count of 1-1 pairs is 𝑘, then the number of rectangles that can be made with those is 𝑘(𝑘-1)/2.

Implementation in JavaScript:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function countRectangles(rect) {
    let count = 0;
    for (let y2 = 1; y2 < rect.length; y2++) {
        for (let y1 = 0; y1 < y2; y1++) {
            let pairs = 0;
            for (let x = 0; x < rect[0].length; x++) {
                if (rect[y1][x] + rect[y2][x] == 2) {
                    pairs++;
                }
            }
            // Count in how many ways 2 pairs of corners can be combined
            count += pairs * (pairs - 1) / 2;
        }
    }
    return count;
}

const rect = [
    [1,  0,  1,  1,  1],
    [1,  1,  0,  0,  1],
    [1,  0,  1,  1,  0],
    [0,  1,  1,  1,  1],
    [1,  0,  1,  1,  1],
]

console.log(countRectangles(rect)); // 22

<!-- end snippet -->

- LOOP C over cells in the matrix
   - LOOP S over possible rectangle sizes, starting from this cell
       - Set found TRUE
       - LOOP R over cells forming rectangle of size S with top left at C
            - IF R contain 0
                  - SET found false
                  - BREAK from LOOP R
       - IF found
            Add to count

Example:

matrix 5 by 5
start cell 1,1  ( zero-based )
maximum rectangle is 4 by 4
check cells at  1,4    4,1    and 4,4
if all contain 1s you have found a 4 by 4 rectangle

Since the complexity will be at least as high as the length of the output anyway, you might as well bruteforce this.

def gen_rectangles(matrix):
  height, width = matrix.shape
  for left in range(width):
    for top in range(height):
      if matrix[top, left] == 1:
        for right in range(left+1, width):
          if matrix[top, right] == 1:
            for bottom in range(top+1, height):
              if matrix[bottom, left] == matrix[bottom, right] == 1:
                yield (top, left, bottom, right)

import numpy as np
matrix = np.array([[int(x) for x in row.split()] for row in
'''1  0  1  1  1
1  1  0  0  1
1  0  1  1  0
0  1  1  1  1
1  0  1  1  1'''.split('\n')])

print(list(gen_rectangles(matrix)))
# [(0, 0, 2, 2), (0, 0, 4, 2), (0, 0, 2, 3), (0, 0, 4, 3), (0, 0, 1, 4), (0, 0, 4, 4), (1, 0, 4, 4), (2, 0, 4, 2), (2, 0, 4, 3), (1, 1, 3, 4), (0, 2, 2, 3), (0, 2, 3, 3), (0, 2, 4, 3), (0, 2, 3, 4), (0, 2, 4, 4), (2, 2, 3, 3), (2, 2, 4, 3), (3, 2, 4, 3), (3, 2, 4, 4), (0, 3, 3, 4), (0, 3, 4, 4), (3, 3, 4, 4)]