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.

An example of a solved grid

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?

  • $\begingroup$ Do you want to find the minimum number of blocks? In that case, in your example case, $8$ blocks are not minimum. $\endgroup$ Dec 28 '21 at 17:16
  • 1
    $\begingroup$ Is $T$ an input? $\endgroup$
    – nir shahar
    Dec 28 '21 at 17:35
  • $\begingroup$ (The most interesting part is blocks of size 1 having no direction.) $\endgroup$
    – greybeard
    Dec 28 '21 at 17:49
  • $\begingroup$ 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. $\endgroup$
    – 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)

  • $\begingroup$ 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. $\endgroup$
    – Vid
    Dec 28 '21 at 19:42
  • $\begingroup$ count only when you go from 0->1 not 1->0. $\endgroup$ Dec 29 '21 at 10:09
  • $\begingroup$ in your example this algo works fine $\endgroup$ Dec 29 '21 at 10:15
  • $\begingroup$ 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. $\endgroup$
    – Vid
    Dec 29 '21 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.