find all rectangular areas with certain properties in a matrix

Question

given an n*m matrix with the possible values of 1, 2 and null:

  . . . . . 1 . .
  . 1 . . . . . 1
  . . . 2 . . . .
  . . . . 2 . . .
  1 . . . . . 1 .
  . . . . . . . .
  . . 1 . . 2 . .
  2 . . . . . . 1

I am looking for all blocks B (containing all values between (x0,y0) and (x1,y1)) that:

• contain at least one '1'
• contain no '2'
• are not a subset of a another block with the above properties

Example:

The red, green and blue area all contain an '1', no '2', and are not part of a larger area. There are of course more than 3 such blocks in this picture. I want to find all these blocks.

what would be a fast way to find all these areas?

I have a working brute-force solution, iterating over all possible rectangles, checking if they fulfill the first two criteria; then iterating over all found rectangles, removing all rectangles that are contained in another rectangle; and I can speed that up by first removing consecutive identical rows and columns. But I am fairly certain that there is a much faster way.

Answer 1

I finally found a solution that works almost in linear time (there is a small factor depending on the number of found areas). I think this is the fastest possible solution.

Inspired by this answer: https://stackoverflow.com/a/7353193/145999 (pictures also taken from there)

First, I go trought the matrix by column, creating a new matrix M1 measuring the number of steps to the last '1' and a matrix M2 measuring the number of steps to the last '2'

imagine a '1' or '2' in any of the grey blocks in the above picture

in the end I have M1 and M2 looking like this:

No go through M1 and M2 in reverse, by row:

I execute the following algorithm:

 foundAreas = new list()

 For each row y backwards:
     potentialAreas = new List()
     for each column x:
        if M2[x,y]>M2[x-1,y]:
            add to potentialAreas: 
                new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false)
        if M2[x,y]<M2[x-1,y]:
            for each area in potentialAreas:
                 if area.hasTop and area.hasOne<area.height:
                        add to foundAreas:
                             new Box(Area.left,y-area.height,x,y)
            if M2[x,y]==0: delete all potentialAreas
            else:
                 find the area in potentialAreas with height=M2[x,y] 
                 or the one with the closest bigger height: set its height to M2[x,y]
                 delete all potentialAreas with a bigger height

            for each area in potentialAreas:
                 if area.hasOne>M1[x,y]: area.hasOne=M1[x,y]
                 if M2[x,y+1]==0: area.hasTop=true

now foundAreas contains all rectangles with the desired properties.

Answer 2

You can get somewhere between considering every rectangle, and a properly clever solution.

For example, starting at each 1 you could create a rectangle and gradually expand its edges outwards in 4 directions. Stop when you hit a 2, record this rectangle if (a) you've had to stop in all 4 directions, and (b) you haven't seen this rectangle before.

Then backtrack: you need to be able to generate both the red rectangle and the green rectangle starting from the 1 near the top left.

This algorithm has some pretty bad worst cases, though. An input consisting of all 1s springs to mind. So it does need to be combined with some other cleverness, or some constraints on the input.

Answer 3

Consider the simpler one dimension problem:

Find all the substrings of .2.1.1...12....2..1.1..2.1..2 which contains at least one 1 and no 2 and are not substring of such string. This can be solved in linear time, you just have to check if there is a 1 between two 2.

Now you can easily adapt this algorithm to the two dimension problem:

For 1≤i≤j≤n sum all lines from i to j using the following law: .+.=., .+1=1, .+2=2, 1+1=1, 1+2=2, 2+2=2 and apply the one dimension algorithm to the resulting line.

Complexity: O(n²m).