Watch 7 video solutions for Row With Maximum Ones, a easy level problem involving Array, Matrix. This walkthrough by Algorithms Casts has 756 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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:
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:
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].
Constraints:
m == mat.length n == mat[i].length 1 <= m, n <= 100 mat[i][j] is either 0 or 1.Problem Overview: You are given a binary matrix where each cell contains either 0 or 1. The task is to return the index of the row that contains the maximum number of 1s and the count of those ones. If multiple rows contain the same maximum number, you return the smallest row index.
Approach 1: Brute Force Row Scan (Time: O(m*n), Space: O(1))
The most direct solution is to iterate through every row and count how many 1s it contains. For each row, loop through all columns and increment a counter whenever you encounter a 1. Keep track of the best result using two variables: maxOnes and rowIndex. Whenever the current row's count exceeds maxOnes, update both values.
This works because the matrix size is small enough that scanning every cell is completely acceptable. The algorithm simply performs a nested iteration: the outer loop walks through rows and the inner loop scans the elements of that row. The total time complexity becomes O(m*n), where m is the number of rows and n is the number of columns. Only a few integer variables are used, so the extra space complexity stays O(1). This approach relies only on basic traversal of a 2D array, making it easy to implement in any language.
Approach 2: Row Sum Using Built-in Aggregation (Time: O(m*n), Space: O(1))
A slightly cleaner variation uses built-in aggregation functions such as sum() in Python or manual accumulation utilities in other languages. Instead of incrementing a counter inside an inner loop, compute the number of ones in a row using a single expression like rowSum = sum(matrix[i]). Then compare that value with the current maximum and update the result if needed.
The algorithm still scans every element of the matrix internally, so the time complexity remains O(m*n). Space usage also stays O(1) since only a few tracking variables are maintained. The advantage is readability: the intent becomes clear immediately—calculate the number of ones in each row and keep the row with the largest total.
Recommended for interviews: Interviewers expect the straightforward row scanning solution. The brute force approach already runs in optimal time because every cell may need to be inspected in the worst case. Focus on writing clean traversal logic, correctly tracking the maximum count, and handling ties by keeping the smallest row index.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Row Scan | O(m*n) | O(1) | General case for any binary matrix. Simple and interview-friendly. |
| Row Sum Using Built-in Aggregation | O(m*n) | O(1) | Cleaner implementation when language provides fast row sum utilities. |