Count particular rectangles in a matrix
Given a matrix with distinct values, a rectangle consists of 4 cells at the intersection of two distinct rows and two distinct columns. It is good if the largest 2 values of the 4, are on the same row or the same column. Count the number of good rectangles in linear time, in the size of the matrix.
Discussion
This is a problem from the warmup competition of ICPC/European Championship 2024. During a discussion between Christoph, Pavel and Aris, the following elegant solution was found by Pavel. Once you have the key idea, the solution is quite simple to implement. The trick is that instead of counting good rectangles we count good triangles. There is a linear equation relating these two quantities.
Key idea
Consider the following illustration of the problem, depicting 3 particular rectangles as an example. The values of the 4 cells are replaced by their rank. The first two rectangles are good, because the two largest cells, of rank 3 and 4, are in the same row or the same column. The third rectangle is bad, because the two largest cells are diagonally opposite.
Now we introduce a different object, namely a triangle. A triangle with corner C, consists of two other cells : a cell A, in the same column as C and a cell B in the same row as C. If the value of C is larger than the values of A and of B, then the triangle is called good.
A rectangle contains 4 triangles, one for each corner cell. If the corner cell has rank 1 or 2, then the triangle is bad. If the corner cell has rank 4, then the triangle is good. And the key observation is:
- The triangle with corner cell of rank 3 in the rectangle, is good if and only if the rectangle is bad.
From triangles to rectangles
The matrix has dimensions $n\times n$. Let $N=n(n-1)$. Then we have the following numbers.
- The number of good rectangles is denoted $R$.
- The number of bad rectangles is denoted $B$.
- The number of pairs of rows is $N/2$. And so is the number of pairs of columns.
- The number of rectangles is $N^2 / 4$.
- We have $R+B = N^2 / 4$.
- The number of good triangles is denoted $T$.
- We have $T=R+2B$.
- Hence $R = N^2/2-T$.
Count the number of good triangles
Process the cells of the given matrix $M$ in order of increasing rank. Maintain a counter for every row and every column of the number of its already processed cells. When processing a cell, the number of triangles with this corner cell is simply the product of the counters for the corresponding row and column.
Complexity
Using bucket sort, we can process the cells of $M$ in order, in linear time. The overall running time is linear in the size of $M$.