2 edited body
source | link

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\\ 506607070008880\end{array} \rightarrow \begin{array}0010402220333300\\ 504402020003330\end{array}$$$$\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.

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\\ 506607070008880\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.

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.

1
source | link

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\\ 506607070008880\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.