Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Row with Most Ones

EASYProblemSolveExternal Links

Description

Given a m × n binary matrix mat, find the 0-indexed 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

Input: mat = [[0, 1], [1, 0]]

Output: [0, 1]

Explanation: Both rows have the same number of ones (1 each). Since row 0 has the smallest index, we return [0, 1].

Example 2

Input: mat = [[0, 0, 0], [0, 1, 1]]

Output: [1, 2]

Explanation: Row 0 has 0 ones, row 1 has 2 ones. Row 1 has the maximum count, so we return [1, 2].

Example 3

Input: mat = [[0, 0], [1, 1], [0, 0]]

Output: [1, 2]

Explanation: Row 0 has 0 ones, row 1 has 2 ones, row 2 has 0 ones. Row 1 has the maximum count, so we return [1, 2].

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 ≤ m, n ≤ 100
  • mat[i][j] is either 0 or 1

Editorial

Optimal Approach - Linear Scan

Intuition

Since we need to find the row with the most ones, the most direct approach is to iterate through each row, count the number of ones, and keep track of the row with the highest count so far.

This is already the optimal approach — every element must be examined at least once since any element could be a 1, so we cannot do better than O(m × n) in the worst case.

We maintain two variables:

  • max_count: the highest count of ones seen so far.
  • max_row: the index of the row with max_count ones.

For each row, we sum its elements (since the matrix is binary, the sum equals the count of ones). If the count is strictly greater than max_count, we update both max_count and max_row. Using strict greater-than (>) ensures that in case of ties, we keep the smallest row index (since we iterate rows in order 0, 1, 2, ...).

Step-by-Step Explanation

Let's trace through with mat = [[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]].

Initialize: max_row = 0, max_count = 0.

Row 0: [0, 0, 0]

  • Count of ones = 0 + 0 + 0 = 0.
  • 0 > 0? No. No update.
  • State: max_row = 0, max_count = 0.

Row 1: [0, 1, 1]

  • Count of ones = 0 + 1 + 1 = 2.
  • 2 > 0? Yes. Update: max_row = 1, max_count = 2.
  • State: max_row = 1, max_count = 2.

Row 2: [1, 0, 0]

  • Count of ones = 1 + 0 + 0 = 1.
  • 1 > 2? No. No update.
  • State: max_row = 1, max_count = 2.

Row 3: [1, 1, 1]

  • Count of ones = 1 + 1 + 1 = 3.
  • 3 > 2? Yes. Update: max_row = 3, max_count = 3.
  • State: max_row = 3, max_count = 3.

Result: [3, 3] — Row 3 has the most ones (3).

Linear Scan — Count Ones in Each Row — Watch as we iterate through each row of the binary matrix, count the ones, and track the row with the maximum count.

Algorithm

  1. Initialize max_row = 0 and max_count = 0.
  2. For each row i from 0 to m-1:
    a. Count the number of ones in row i (sum the elements).
    b. If count > max_count: set max_count = count and max_row = i.
  3. Return [max_row, max_count].

Code

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

class Solution {
public:
    vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
        int maxRow = 0, maxCount = 0;
        
        for (int i = 0; i < mat.size(); i++) {
            int count = 0;
            for (int j = 0; j < mat[i].size(); j++) {
                count += mat[i][j];
            }
            if (count > maxCount) {
                maxCount = count;
                maxRow = i;
            }
        }
        
        return {maxRow, maxCount};
    }
};
class Solution:
    def rowAndMaximumOnes(self, mat: list[list[int]]) -> list[int]:
        max_row = 0
        max_count = 0
        
        for i in range(len(mat)):
            count = sum(mat[i])
            if count > max_count:
                max_count = count
                max_row = i
        
        return [max_row, max_count]
class Solution {
    public int[] rowAndMaximumOnes(int[][] mat) {
        int maxRow = 0, maxCount = 0;
        
        for (int i = 0; i < mat.length; i++) {
            int count = 0;
            for (int j = 0; j < mat[i].length; j++) {
                count += mat[i][j];
            }
            if (count > maxCount) {
                maxCount = count;
                maxRow = i;
            }
        }
        
        return new int[]{maxRow, maxCount};
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We visit every element in the matrix exactly once. With m, n ≤ 100, this is at most 10,000 operations.

Space Complexity: O(1)

We only use two extra variables (max_row and max_count), regardless of input size.