Finding sequences of 0's in a 2D binary grid

Question

Requirements:

Given a 2D array of 1's and 0's (black and white cells) find blocks of white cells of size 1xT or Tx1 where T >= 1. Any block should not be a subset of a larger block. Return the number of these blocks.

This is an example solution of a 5x3 grid. There should be 8 blocks. Block y:1, x:0 is not a block because it would be a subset of a bigger block y:1->3, x:0.

What I've tried so far

I've developed a pretty inefficient solution where I iterate through all white cells and for each one get a vertical and horizontal block. Then only accept either block if it isn't a subset of an already accepted block.

The most time complex operation in my code is checking whether a block is a subset of another accepted block.

My questions

What would be a more efficient solution to this problem?

Is there a data structure that would help me with this?

Answer 1

you can solve it easily in O(mn). where m*n is matrix dimension. first consider only 1*T type blocks.

iterate each row and in any row whenever you see a 0->1 consecutive element increase your block count by 1. (if first element of row is 1 then also increase count) similarly, do this on columns.

(here don't consider 1*1 blocks initially in any iteration. finally after iterating over all rows and columns. check for 1*1 blocks separately)

Answer 2

I fail to see any difficulty in this exercise.

Scan every row in turn, in any order. In a row, scan every column from left to right (or conversely), start a block and increment the counter when you meet a white, and end the block when you meet a black or the end of the row.

Scan every column in turn, in any order. In a column, scan every row from top to bottom (or conversely), start a block and increment the counter when you meet a white, and end the block when you meet a black or the end of the column.

Answer 3

I have to agree with both the suggestions by Yves Daoust and Ashish gupta. The following observations should hold:

• A $1 \times S$ block can only be a subset of a $T \times 1$ block if $ S = 1 $.
• An $S \times 1$ block can only be a subset of a $1 \times T$ block if $ S = 1 $.
• Only isolated $ 1 \times 1 $ blocks (without white neighbors) are not subsets of a larger blocks.
• $ 1 \times T $ blocks in different rows can never be subsets of one another.
• $ T \times 1 $ blocks in different columns can never be subsets of one another.

This should allow You to split the block finding as follows:

1. Find $ 1 \times T $ blocks for $ T > 1 $ in each row separately
2. Find $ T \times 1 $ blocks for $ T > 1 $ in each column separately
3. Find all isolated $ 1 \times 1 $ blocks

Both 1. and 2. can both be reduced to the same 1D problem. The following Python code finds all white segments longer than 1 in a 1D array:

import numpy as np


def find_segments( array_1d ):
  array_1d = np.asarray(array_1d, dtype=bool)
  assert array_1d.ndim == 1

  # append black block for simplicity
  # (otherwise last segment needs separate handling)
  array_1d = np.append(array_1d, 1)

  start = None

  for i,ai in enumerate(array_1d):
    if start is None and ai == 0:
      # segment start found
      start = i

    if start is not None and ai == 1:
      # segment end found
      end = i-1
      if start < end: # <- only accept segments greater than 1 
        yield (start,end) 
      start = None

    i += 1

Finding isolated $ 1 \times 1 $ blocks should be as simple as going through each blocks and looking at its neighbors:

def find_1x1_blocks( array_2d ):
  array_2d = np.asarray(array_2d, dtype=bool)
  assert array_2d.ndim == 2

  # pad with black for simplicity
  array_2d = np.pad(array_2d, 1, constant_values=1)

  for (i,j),aij in np.ndenumerate(array_2d):
    if(
      aij == 0
      and array_2d[i-1,j  ] == 1 # <- North 
      and array_2d[i,  j+1] == 1 # <- East
      and array_2d[i+1,j  ] == 1 # <- South
      and array_2d[i,  j-1] == 1 # <- West
    ):
      # subtract padding
      i -= 1
      j -= 1
      yield (i,j)

Using these two subroutines together, we should be able to find all blocks without duplicates:

def find_all_blocks( array_2d ):  
  array_2d = np.asarray(array_2d, dtype=bool)
  assert array_2d.ndim == 2

  (m,n) = array_2d.shape

  # search rows
  for i in range(m):
    for (j,k) in find_segments(array_2d[i,:]):
      yield { 'y': i, 'x': (j,k) }

  # search columns
  for k in range(n):
    for (i,j) in find_segments(array_2d[:,k]):
      yield { 'y': (i,j), 'x': k }

  # collect 1x1 blocks
  for (i,j) in find_1x1_blocks(array_2d):
    yield { 'y': i, 'x': j }

All that's left now is to count the blocks. Let's use Your example:

input = np.array(
  [[1,0,0],
   [0,1,0],
   [0,0,1],
   [0,0,0],
   [1,0,0]]
)

blocks = [*find_all_blocks(input)]

for block in blocks:
  print(block)
# Output:
# {'y': 0, 'x': (1, 2)}
# {'y': 2, 'x': (0, 1)}
# {'y': 3, 'x': (0, 2)}
# {'y': 4, 'x': (1, 2)}
# {'y': (1, 3), 'x': 0}
# {'y': (2, 4), 'x': 1}
# {'y': (0, 1), 'x': 2}
# {'y': (3, 4), 'x': 2}

print(len(blocks))
# Output: 8