Row With Maximum Ones - Solution & Explanation
Problem Statement
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.lengthn == mat[i].length1 <= m, n <= 100mat[i][j]is either0or1.
Approach Overview
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 1: Brute Force Approach
This approach iterates through each row of the matrix, counts the number of ones in each row, and keeps track of the row with the maximum number of ones.
The function findRowWithMaxOnes iterates over each row, counts the number of ones, and updates the maximum count and corresponding row index if the current count exceeds the maximum recorded so far.
Complexity
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no extra space is used.
Approach 2: Simulation
We initialize an array ans = [0, 0] to store the index of the row with the most 1s and the count of 1s.
Then, we iterate through each row of the matrix:
- Compute the number of
1s in the current row, denoted ascnt(since the matrix contains only0s and1s, we can directly sum up the row). - If
ans[1] < cnt, updateans = [i, cnt].
After finishing the iteration, we return ans.
The time complexity is O(m times n), where m and n are the number of rows and columns in the matrix, respectively. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. |
| Simulation | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Row With Maximum Ones - Leetcode 2643 - Python • Algorithms Casts • 784 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Row With Maximum Ones easy or hard?
Row With Maximum Ones Python/Java solution
How to solve Row With Maximum Ones in O(n)?
What is the best approach for Row With Maximum Ones?
Is Row With Maximum Ones asked at Google/Amazon/Meta?
What data structure is used in Row With Maximum Ones?
What is the time complexity of Row With Maximum Ones?
Ready to solve this problem?
Practice Row With Maximum Ones with our built-in code editor and test cases.
Practice on FleetCode