Problem

Given a m x n binary matrix mat, find the 0-indexed position of the row that contains the maximum count of ones, and the number of ones in that row.

In case there are multiple rows that have the maximum count of ones, the row with the smallest row number should be selected.

Return an array containing the index of the row, and the number of ones in it.

Examples

Example 1:

1
2
3

Input: mat = [[0,1],[1,0]]
Output: [0,1]
Explanation: Both rows have the same number of 1's. So we return the index of the smaller row, 0, and the maximum count of ones (1`)`. So, the answer is [0,1].

Example 2:

1
2
3

Input: mat = [[0,0,0],[0,1,1]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones `(2)`. So we return its index, `1`, and the count. So, the answer is [1,2].

Example 3:

1
2
3

Input: mat = [[0,0],[1,1],[0,0]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So the answer is [1,2].

Solution

Method 1 - Iteration

The naive approach to solve this involves iterating through each row in the matrix, counting the number of 1s in each row, and keeping track of the row with the highest count. We can use a simple comparison to record the maximum count and the corresponding row index.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def row_with_max_ones(self, mat: List[List[int]]) -> List[int]:
        max_ones = 0
        ans = [-1, 0]
        
        for i, row in enumerate(mat):
            count_ones = row.count(1)
            if count_ones > max_ones:
                max_ones = count_ones
                ans = [i, count_ones]
            elif count_ones == max_ones and ans[0] == -1:
                ans = [i, count_ones]
                
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int[] rowWithMaxOnes(int[][] mat) {
        int maxOnes = 0;
        int[] ans = {-1, 0};

        for (int i = 0; i < mat.length; i++) {
            int countOnes = 0;
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 1) {
                    countOnes++;
                }
            }
            if (countOnes > maxOnes) {
                maxOnes = countOnes;
                ans[0] = i;
                ans[1] = countOnes;
            } else if (countOnes == maxOnes && ans[0] == -1) {
                ans[0] = i;
                ans[1] = countOnes;
            }
        }

        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n)
  • 🧺 Space complexity: O(1)