CODEWITHSUNDEEP
algorithmdictionarygridblocksubmatrix
chris k.
chris k.

Reputation: 13

Algorithm - Grid Map find number of sub-blocks with specific property

I have a grid map NxN. Each cell may have the value '0' or '1'. I am trying to find the exact number of distinct rectangle sub-blocks of the map that include a specific number of '1' and this number can be between 1 and 6. I have thought of searching for each possible rectangle but this is very slow for a map of size 500x500 and the solution must be ~ 1 sec for a common desktop computer. Can someone tell me a corresponding problem so I can look for a working algorithm or better can someone suggest me a working algorithm for this problem? Thank you all in advance!

Upvotes: 0

Views: 104

Answers (1)

user4843530
user4843530

Reputation:

I imagine that your search of all the rectangles is slow because you are actually counting on each possible rectangle. The solution to this is not to count all rectangles, but rather create a second array of NxN which contains the count for the rectangle (0,0..x,y), call this OriginCount. Then to calculate the count for any given rectangle, you will not have to go through the rectangle and count. You can simply use

Count(a,b..c,d) = OriginCount(c,d) + OriginCount(a-1,b-1) -
                  OriginCount(a-1,d) - OriginCount(c,b-1)

That turns the problem of counting the ones in any given rectangle, from an N2 problem to a discrete or constant time problem, and your code gets in the order of thousands times faster (for your 500x500 case)

Mind you, in order to set up the OriginCount array, you can use the same concept, don't just go count the ones for each rectangle, from 0,0 to x,y. Rather, use the formula

OriginCount(x,y) = OriginCount(x-1,y) + OriginCount(x,y-1) - OriginCount(x-1,y-1) +
                   GridMap(x,y) == 1 ? 1 : 0;

Mind you, you have to account for edge cases - where x=0 or y=0.

Upvotes: 2

Related Questions