CODEWITHSUNDEEP
c++calgorithmmatrix
user1002288
user1002288

Reputation: 5040

Find the row(s) with maximum number of 0s in a 2-d matrix

Problem

Given a 2D 0/1 Matrix, Find the row(s) with maximum number of 0s.

Example

11111000
11111110
11100000
11000000
11110000

Output

11000000

My idea

If each 0s row is continuous, we can scan from two ends for each row. Common sense says to scan with O(n^2).

Are there any O(n) solutions?

Upvotes: 1

Views: 2403

Answers (5)

Mateen Ulhaq
Mateen Ulhaq

Reputation: 27201

As @amit says:

scanning a matrix is considered O(n). The standard big O notation stands for relationship between run time and the input size. Since your input is of size #rows*#cols, you should regard this number as n, and not to #rows.

Therefore, this is as O(n) as you can get. :)

std::vector<std::string> matrix;
std::vector<std::string>::iterator max = matrix.begin();

for(std::vector<std::string>::iterator i = matrix.begin(); i != matrix.end(); ++i)
{
    if(count_zeros(*i) > count_zeros(*max))
        max = i;
}

count_zeros() should look something like this:

size_t count_zeros(std::string s)
{
    size_t count = 0;

    for(std::string::iterator i = s.begin(); i != s.end(); ++i)
        if(*i == '0')
            ++count;

    return i;
}

If all the 0s in each row are guaranteed to be at the rightmost, you can do it in O(sqrt(n)).

  1. Put cursor on (len, 0)
  2. If the value to the left of the cursor is 0, move the cursor left. Else, move it down.
  3. If bottom row is reached, terminate. Else, go to step 2.
std::vector<std::string> matrix;
std::vector<std::string>::iterator y = matrix.begin();

for(std::string::reverse_iterator x = (*y).rbegin(); x < matrix.rend(); )
{
    if(*x != '0')
    {
        x -= (*y).rbegin();
        ++(*y);
        x += (*y).rbegin();
        continue;
    }

    ++x;
}

Upvotes: 1

gilgamash
gilgamash

Reputation: 902

Here a quick solution with just one if or each row (not for each element): As your matrix just holds zeros and ones, add up the elements of each row and then return the index/indices of the minimum/minimae.

P.S.: adding ones is really fast when using assmbly inc or ++Variable in C++

Edit: Here another idea. If you really just need 0/1 matrices that do not excedd say 64 columns, you could implement them as bit matrices using ordinary unsigned 64 integers. By setting and deleting the respective bit you can define the entry (0 or 1). The effect: an o(n) check (let me know if I am wrong) as followsm, where intXX is rowXX. The first idea is to extract different bits via XOR

SET tmpA to int01
FOR I = 1 to n-1
  XOR intI with intI+1, store result in tmpX
  AND tmpX with intI, store result in tmpM
  AND tmpX with intI+1, store result in tmpN
  if (tmpN < tmpM)
    SET tmpA to intI+1
ENDFOR

tmpA should now hold the (last) row with fewest zeros.

Cheers, G.

Upvotes: 0

Soren
Soren

Reputation: 14688

With the give sample set (were all starts with 111 and ends in 000 with no mix of 1 and 0) the set can simply be searched in a single pass with a test of A&(A xor B) for testing if there are more or less zero than the previous row -- that is a loop of O(n)....

Upvotes: 0

Ravi Gupta
Ravi Gupta

Reputation: 6460

You can do it in O(N) as follows:

Start at A[i][j] with i=0 and j=No_of_columns-1.

           0, keep moving to the left by doing j--
A[i][j] = 
           1, move down to the next row by doing i++

When you reach the last row or the last column, the value of j will be the answer.

Pseudo code:

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = C-1   
Let max1Row = 0

while ( i<R && j>=0 )
   if ( matrix[i][j] == 0 )
      j--
      max1Row = i
   else
      i++
end-while


print "Max 0's = j"
print "Row number with max 0's = max1Row"

Upvotes: 1

l2y3n2
l2y3n2

Reputation: 76

if every row is like 1....10...0, you could binary search first zero in each row.

That would be O(n*lg(n))

for an arbitrary matrix, you must check every cell, so it must be O(n^2).

Upvotes: 1

Related Questions