Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How many subrectangle exists on a m x n grid

Tags:

algorithm

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.

like image 473
q0987 Avatar asked Jul 29 '13 15:07

q0987


1 Answers

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

like image 133
Thomash Avatar answered Sep 19 '22 08:09

Thomash