Matrix: Given a binary matrix, find the rows with max 1s

Coding Interview Questions

1 min read

Problem Statement:

Given a matrix, you need to find the row with maximum 1s.

Each rows are sorted

Example:

Input:

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

Output: 1

Solution :

Solution is very simple.

we go row by row and count the max 1s.

Finally return with max 1s.

Time Complexity: O(m * n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

#define N 4 // row
#define M 4 // column

int solution(vector<vector<bool>>& mat) 
{

    int rowIndex = -1;
    int maxCount = 0;
    int m = mat.size();
    int n = mat[0].size();

    for (int i = 0; i < n; i++) 
    {
        int count = 0;
        for (int j = 0; j < m; j++) 
        {
            if (mat[i][j] == 1) 
            {
                count++;
            }
        }
        if (count > maxCount) 
        {
            maxCount = count;
            rowIndex = i;
        }
    }

    return rowIndex;
}


int main() {
    vector<vector<bool>> mat = {{0, 0, 0, 1},
                                {1, 1, 1, 1},
                                {1, 1, 0, 0},
                                {0, 0, 0, 0}};

    cout << solution(mat);
    return 0;
}