Given a m x n
grid, how many unique sub-rectangles exist on such a grid?
For example,
1 x 1
grid has 1 sub-rectangle.
1 x 2
grid has 3 sub-rectangles.
I am looking for a general formula that can be used to directly compute the number existing sub-rectangle.
The answer is m(m+1)n(n+1)/4
.
a rectangle is defined by its two projections on the x-axis and on the y-axis.
projection on x-axis : number of pairs (a,b) such that 1 <= a <= b <= m = m(m+1)/2
idem for y-axis
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With