-2

Input:

[1, 0, 1],
[0, 1, 0],
[1, 0, 1]

Output: [2, 1, 2]

For this example, n = number of rows or columns

For the given binary matrix, can I get an array of the count of 1's in each row in O(n) time complexity?

Rahul Malpani
  • 1
  • 1
  • Have you tried just using `count()`? : `[l.count(1) for l in list_of_lists]`. Alternatively just a sum: `list(map(sum, list_of_lists))`? – Mark Jan 10 '22 at 04:17
  • Yes. Loop over each row, and count the number of zeros in that row. Of course, I'm assuming you mean `N` to be the size of the matrix – juanpa.arrivillaga Jan 10 '22 at 04:17
  • Does `n` refer to the number of rows/columns in the matrix? – BrokenBenchmark Jan 10 '22 at 04:18
  • 3
    There is no way of solving this problem without looking at every element of the array. Hence the fastest algorithm is one that looks at every element once and several versions of that algorithm have been shown to you. As others have said, your question is ambiguous, what do you mean by `n`? – Frank Yellin Jan 10 '22 at 04:22
  • n refers to number of rows – Rahul Malpani Jan 10 '22 at 04:24
  • you can in parallel add the ith element of each horizontal row if each one is stored as a contiguous array. – Omar Abdel Bari Jan 10 '22 at 04:25
  • 2
    Pick a language, make an attempt, post a [mcve] when it fails. – Mad Physicist Jan 10 '22 at 04:29
  • 2
    The way you stated the problem there is probably no O(n) solution. But there are constant time solutions for [bit counting](https://stackoverflow.com/a/8871435/14277722). Depending on the implementation of the binary matrix, you can calculate your desired output array in O(n) in special/limited cases. – Michael Szczesny Jan 10 '22 at 05:27

1 Answers1

1

If N is the number of rows, then there is no O(N) solution. You need to visit each cell. There are N^2 cells so the complexity is O(N^2).

If you represent the matrix using bits (0 or 1) rather than integer counts, you can do the bit counting faster than iterating the bits. However, there are still O(N^2) bits in the matrix. Even if you pack them 32 or 64 bits per word, you still have O(N^2) words to visit... so the complexity remains the same.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216