1
$\begingroup$

I am interested in finding the rows of a matrix where all entries are equal to zeros except for one.

Example: Given the following matrix:

\begin{bmatrix}0 &0 &3 & 8\\ 0 & 4 & 0 & 0 \\ 0 &1 & 0 & 1\end{bmatrix}

Only the second line has this property.

Of course, the brute force way is to go over the entries and check them one by one. But I am wondering if there is another most efficient way I don't know about.

$\endgroup$
1
$\begingroup$

There is no algorithm with worst-case running time better than $O(n^2)$. There is a simple adversary argument to prove this.

Consider any algorithm that is purported to be correct, and that always inspects fewer than $n^2$ entries of the matrix. Thus, there must always be some entry that is uninspected. Consider a matrix that has 1's in the entire first column. Every time the algorithm inspects any other entry, it will find a 0. After inspecting at most $n^2-1$ entries, the algorithm terminates and outputs some list of rows. Pick any entry that was uninspected. Now we have a freedom about whether to fill it in with a 0 or a 1; and we can always make a choice that will make the algorithm's output wrong (if the algorithm included that row in its output, make it a 1; otherwise make it a 0). So, for any correct algorithm, it must inspect all matrix entries for at least some inputs, so its running time must be at least $\Omega(n^2)$.

There are various optimizations you can use in practice, like using bitwise operations (depending on how the matrix is stored), and if you see more than a single 1 in any row, don't look at any other entries in that row -- but these won't affect the asymptotic worst-case running time.

$\endgroup$
1
$\begingroup$

This is no different than asking for an algorithm for deciding if the entries of an array contain a nonzero. So what you describe is optimal, i.e. an adversary argument shows that any algorithm must examine each entry for otherwise you can't know for sure.

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