Efficient way to find all zeros in a matrix?

Question

I am thinking of efficient algorithm to find the number of zeros in a row of matrix but can only think of O(n²) solution (i.e by iterating over each row and column). Is there a more efficient way to count the zeros?

For example, given the matrix

3,  4,  5,  6
7,  8,  0,  9
10, 11, 12, 3
4,  0,  9,  10 

I would report that there are two zeros.

Answer 1

For any un sorted matrix it should be O(n). Since generally we represent total elements with 'n'.

If Matrix contains X Rows and Y Columns, X by Y = n.

E.g In 4 X 4 un sorted matrix it total elements 16. so When we iterate in linear with 2 loops 4 X 4 = 16 times. it will be O(n) because the total elements in the array are 16.

Many people voted for O(n^2) because they considered n X n as matrix.

Please correct me if my understanding is wrong.

Answer 2

assuming the given Matrix is M do an M+(-M) operation but do use the default + use instead my_add(int a, int b) such that

int my_add(int a, int b){
  return (a == b == 0) ? 1 : (a+b);      
}

That will give you a matrix like

0  0  0  0
0  0  1  0
0  0  0  0
0  1  0  0

Now you create a s := 0 and keep adding all elements to s. s += a[i][j]

You can do both in one cycle even. s += my_add(a[i][j], (-1)*a[i][j])

But still Its O(m*n)

NOTE

To count the number of 1's you generally check all items in the Matrix. without operating on all elements I don't think you can tell the number of 1's. and to loop all elements its (m*n). It can be faster than (m*n) if and only if you can leave some elements unchecked and say the number of 1's

EDIT

However if you move a 2x2 kernel over the matrix and hop you will get (m*n)/k iteration e.g. if you operate on neighboring elements a[i][j], a[i+1][j], a[i][j+1], a[i+1][j+1] till i < m & i< n

Answer 3

This is not a perfect answer for the reasons I'll explain, but it offers an alternative solution potentially faster than the one you described:

1. Since you don't need to know the position of the zeros in the matrix, you can flatten it into a 1D array.

2. After that, perform a quicksort on the elements, this may provide a performance of O(n log n), depending on the randomness of the matrix you feed in.

3. Finally, count the zero elements at the beginning of the array until you reach a non-zero number.

In some cases, this will be faster than checking every element, although in a worst-case scenario the quicksort will take O(n2), which in addition to the zero counting at the end may be worse than iterating over each row and column.

Answer 4

Always O(n^2) - or rather O(n x m). You cannot jump over it.

But if you know that matrix is sparse (only a few elements have nonzero values), you can store only values that are non zero and matrix size. Then consider using hashing over storing whole matrix - generally create hash which maps a row number to a nested hash.

Example:

m = 
[ 
  0 0 0 0
  0 2 0 0
  0 0 1 0
  0 0 1 0
]

Will be represented as:

row_numbers = 4
column_numbers = 4
hash = { 1 => { 1 => 2}, 2 => {2 => 1, 3 => 2}}

Then:

number_of_zeros = row_numbers * column_numbers - number_of_cells_in_hash(hash)

Answer 5

Without storing any external information, no, you can't do any better than Θ(N²). The rationale is simple - if you don't look at all N² locations in the matrix, then you can't guarantee that you've found all of the zeros and might end up giving the wrong answer back. For example, if I know that you look at fewer than N² locations, then I can run your algorithm on a matrix and see how many zeros you report. I could then look at the locations that you didn't access, replace them all with zeros, and run your algorithm again. Since your algorithm doesn't look at those locations, it can't know that they have zeros in them, and so at least one of the two runs of the algorithm would give back the wrong answer.

More generally, when designing algorithms to process data, a good way to see if you can do better than certain runtimes is to use this sort of "adversarial analysis." Ask yourself the question: if I run faster than some time O(f(n)), could an adversary manipulate the data in ways that change the answer but I wouldn't be able to detect? This is the sort of analysis that, along with some more clever math, proves that comparison-based sorting algorithms cannot do any better than Ω(n log n) in the average case.

If the matrix has some other properties to it (for example, if it's sorted), then you might be able to do a better job than running in O(N²). As an example, suppose that you know that all rows of the matrix are sorted. Then you can easily do a binary search on each row to determine how many zeros it contains, which takes O(N log N) time and is faster.

Depending on the parameters of your setup, you might be able to get the algorithm to run faster if you assume that you're allowed to scan in parallel. For example, if your machine has K processors on it that can be dedicated to the task of scanning the matrix, then you could split the matrix into K roughly evenly-sized groups, have each processor count the number of zeros in the group, then sum the results of these computations up. This ends up giving you a runtime of Θ(N² / K), since the runtime is split across multiple cores.

Answer 6

Assuming that when you say "in a row of a matrix", you mean that you have the row index i and you want to count the number of zeros in the i-th row, you can do better than O(N^2).

Suppose N is the number of rows and M is the number of columns, then store your matrix as a single array [3,4,5,6,7,8,0,9,10,11,12,34,0,9,10], then to access row i, you access the array at index N*i.

Since arrays have constant time access, this part doesn't depend on the size of the matrix. You can then iterate over the whole row by visiting the element N*i + j for j from 0 to N-1, this is O(N), provided you know which row you want to visit and you are using an array.