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

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?

• Do you want to find the minimum number of blocks? In that case, in your example case, $8$ blocks are not minimum. Dec 28 '21 at 17:16
• Is $T$ an input? Dec 28 '21 at 17:35
• (The most interesting part is blocks of size 1 having no direction.) Dec 28 '21 at 17:49
• Maximum number of blocks, not minimum. T is not an input. Direction doesn't matter so blocks of size 1 can be in row or column direction.
– Vid
Dec 28 '21 at 18:59

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)

• Unless I'm missing something this only works for a few problems. Here's an example of an incorrect solution with this algorithm: i.imgur.com/hb5a9Zc.jpg Red is correct solution (5), blue is your algorithm.
– Vid
Dec 28 '21 at 19:42
• count only when you go from 0->1 not 1->0. Dec 29 '21 at 10:09
• in your example this algo works fine Dec 29 '21 at 10:15
• Your algorithm only works for the one example I provided, but with a few modifications it does work for all of my test cases as well.
– Vid
Dec 29 '21 at 11:30