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