9
$\begingroup$

Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ entries.

The original question was to count the number of islands in a given matrix. The author described a recursive solution ($\mathcal{O}(nm)$ memory).

But I was unsuccessfully trying to find a streaming (left to right, and then down to the next row) solution that dynamically counts islands with $\mathcal{O}(m)$ or $\mathcal{O}(n)$ or $\mathcal{O}(n+m)$ memory (there are no limits for the time complexity). Is that possible? If not, how can I prove it?


A few examples of expected outputs for certain inputs for the count function:

$ count\begin{pmatrix} 010\\ 111\\ 010\\ \end{pmatrix} = 1; % count\begin{pmatrix} 101\\ 010\\ 101\\ \end{pmatrix} = 5; % count\begin{pmatrix} 111\\ 101\\ 111\\ \end{pmatrix} = 1; $

$ count\begin{pmatrix} 1111100\\ 1000101\\ 1010001\\ 1011111\\ \end{pmatrix} = 2$

$ count\begin{pmatrix} 101\\ 111\\ \end{pmatrix} = 1$

$\endgroup$
  • 1
    $\begingroup$ 1. What do you mean by "orthogonal"? Do you mean a connected component? 2. What can we assume about how the matrix is stored? Can we assume it is stored on external storage (e.g., a slow hard disk), so you can read any portion you want, but it will be faster to read it a block at a time? Or do we receive the matrix in a streaming fashion, where once we've received a bit of the input matrix we can never see that bit of input again? $\endgroup$ – D.W. May 2 '17 at 7:23
  • 1
    $\begingroup$ Cool, thanks. I encourage you to edit the question to clarify those points. If it's streaming, what order do the bits of the matrix arrive in? Scanning left to right among a row, then down to the next row? $\endgroup$ – D.W. May 2 '17 at 7:41
  • 1
    $\begingroup$ Please edit the question to include all these details. Comments are ephemeral. $\endgroup$ – Yuval Filmus May 2 '17 at 9:41
  • 2
    $\begingroup$ Not all information given in the comments can be found in the post itself. Some of this information is rather crucial, like your streaming model. Comments could disappear, and so (and due to community standards), all requisite details should form part of the main post. $\endgroup$ – Yuval Filmus May 2 '17 at 10:04
  • 1
    $\begingroup$ What is the required time complexity? $\endgroup$ – hengxin May 2 '17 at 11:22
4
$\begingroup$

Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual complexity is $O(\min(m, n))$ memory. Processing time is $O(mn)$.

  1. Initialization. Scan over the first row and find all connected substrings of that row. Assign each disjoint substring a unique positive id and save this as a vector which is zero where $X$ is zero and the unique positive id otherwise.

  2. For each remaining row assign unique ids (never re-assign previous unique ids, make sure that your ids are strictly increasing) to substrings in that row again. View the previous row plus the current row as a $2$ by $m$ matrix, and any connected areas should be assigned to their minimum. As an example:

    $$\begin{array}0010402220333300\\ 506607080009990\end{array} \rightarrow \begin{array}0010402220333300\\ 504402020003330\end{array}$$

    There's no need to update the previous row for the correctness of this algorithm, only current one.

    After that's done, find the set of all ids in the previous row that do not connect to the next row, discarding duplicates. Add the size of this set to your running counter of islands.

    You can now discard the previous row and assign the current row to the previous row and move on.

  3. To correctly handle the last row pretend there is another row of zeros at the bottom of $X$ and run step 2 again.

$\endgroup$
6
$\begingroup$

Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed by reducing set disjointness to your problem.

Suppose that Alice holds a binary vector $x_1,\ldots,x_n$ and Bob holds a binary vector $y_1,\ldots,y_n$, and they want to know whether there exists an index $i$ such that $x_i=y_i=1$. They run your algorithm for the $2\times(2n-1)$ matrix whose rows are $x_1,0,x_2,0,\ldots,0,x_n$ and $y_1,0,y_2,0,\ldots,0,y_n$. After the first row is read, Alice sends Bob $\sum_i x_i$ as well as the memory contents, so that Bob can complete the algorithm and compare $\sum_i (x_i+y_i)$ to the number of connected components. If the two numbers match, the two vectors are disjoint (there is no index $i$), and vice versa. Since any protocol for set disjointness needs $\Omega(n)$ bits (even if it can err with a small constant probability), we deduce an $\Omega(n)$ lower bound, which holds even for randomized protocols which are allowed to err with some small constant probability.

We can improve on Orlp's solution by using noncrossing partitions. We read the matrix row by row. For each row, we remember which 1s are connected via paths going through preceding rows. The corresponding partition is noncrossing, and so can be encoded using $O(n)$ bits (since noncrossing partitions are counted by Catalan numbers, whose growth rate is exponential rather than factorial). When reading the following row, we maintain this representing, and increase a counter whenever all ends of some part are not connected to the current row (the counter takes an additional $O(\log n)$ bits). As in Orlp's solution, we add a final dummy row of zeroes to finish processing the matrix. This solution uses $O(n)$ bits, which is asymptotically optimal given our lower bound.

$\endgroup$

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.