Find index of the row containing maximum number of 1's in a binary matrix

Given a binary M x N row-wise sorted matrix, find a row which contains maximum number of 1 in linear time.

For example,

Input:

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

Output: Maximum 1’s are present in the row 4

The idea is to start from the top-right corner of the matrix and do the following

– if current cell has value 1, continue moving left till we encounter 0 or all columns are processed, else
– if current cell has value 0, continue moving down till we encounter 1 or all rows are processed.

Finally, we return the row index of last cell in which we have seen 1.

C++ implementation –

#include <iostream>
using namespace std;

#define M 5
#define N 5

int findRowIndex(bool mat[][N])
{
    // i, j stores current row and column index
    int i, j;
    
    // stores row number with maximum index
    int row = -1;

    // start from top-rightmost cell of the matrix
    i = 0, j = N - 1;
    
    while (i <= M - 1 && j >= 0)
    {
        // move left if current cell has value 1
        if (mat[i][j])
            j--, row = i;    // update row number
        else    // else move down
            i++;
    }

    return row + 1;
}

int main()
{
    bool mat[M][N] = 
    {
        { 0, 0, 0, 1, 1 },
        { 0, 0, 1, 1, 1 },
        { 0, 0, 0, 0, 0 },
        { 0, 1, 1, 1, 1 },
        { 0, 0, 0, 0, 1 } 
    };

    int rowIndex = findRowIndex(mat);

    // rowIndex = 0 means no 1's are present in the matrix
    if (rowIndex)
        cout << "Maximum 1's are present in the row " << rowIndex;

    return 0;
}

#include <iostream>

using namespace std;

#define M 5

#define N 5

int findRowIndex(bool mat[][N])

{

// i, j stores current row and column index

int i, j;

// stores row number with maximum index

int row = -1;

// start from top-rightmost cell of the matrix

i = 0, j = N - 1;

while (i <= M - 1 && j >= 0)

{

// move left if current cell has value 1

if (mat[i][j])

j--, row = i; // update row number

else // else move down

i++;

}

return row + 1;

}

int main()

{

bool mat[M][N] =

{

{ 0, 0, 0, 1, 1 },

{ 0, 0, 1, 1, 1 },

{ 0, 0, 0, 0, 0 },

{ 0, 1, 1, 1, 1 },

{ 0, 0, 0, 0, 1 }

};

int rowIndex = findRowIndex(mat);

// rowIndex = 0 means no 1's are present in the matrix

if (rowIndex)

cout << "Maximum 1's are present in the row " << rowIndex;

return 0;

}

Download Run Code

Output:

Maximum 1’s are present in the row 4

The time complexity of above solution is O(M + N) and auxiliary space used by the program is O(1).

1 Star 2 Stars 3 Stars 4 Stars 5 Stars (2 votes, average: 5.00 out of 5)

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

newest oldest most voted

Guest

arandomguy

Share On Twitter Share On Google

what is the logic behind this? How does it work correctly?

ok got it. didn’t read the problem carefully “row wise sorted binary matrix”.

Aron

I dont think this is right..you only move down if you hit a 0 in the very last element in every row.. therefore you get 2. I tried the exact code and it didn’t work. Second of all, how is the complexity O(N+M) ? You are going through the matrix row-wise and column-wise. I think it’s O(N*M).

Aditya

Code works fine. I think you’re confused somewhere. Please read the problem statement again and try to relate the logic. If you still think you’re right, kindly provide a test case where the code fails.
Also time complexity remains O(N+M) since we either go left or bottom, and not in other two directions at any point.

Nikolay

Sorry, just made the same mistake as arandomguy below. The solution is correct.

Find index of the row containing maximum number of 1’s in a binary matrix

Leave a Reply

Sharing is caring:

Leave a Reply