Row With Maximum Ones — Solution in Python, Java & C++
Row With Maximum Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Row With Maximum Ones is an easy coding problem on arrays and matrix, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an m × n binary matrix mat, find the row with the most ones.
Return [rowIndex, count]. If several rows tie, return the one with the smallest index.
Example 1
Input: mat = [[0,1],[1,0]]
Output: [0,1]
Explanation: Both rows hold one 1, so the smaller index wins.
Example 2
Input: mat = [[0,0,0],[0,1,1]]
Output: [1,2]
Example 3
Input: mat = [[0,0],[1,1],[0,0]]
Output: [1,2]
Constraints
1 <= mat.length, mat[i].length <= 8mat[i][j] is 0 or 1.
Hints for Row With Maximum Ones
Hint 1
Since the entries are 0 and 1, a row's count of ones is just its sum.
Hint 2
Scan top to bottom and replace the best only on a strictly greater count — that is what keeps the smallest index on a tie.
How to solve Row With Maximum Ones
Each row's ones count is its sum; scan top to bottom and replace the best only on a strictly greater count.
Approach
- For each row, compute its sum.
- If the sum is greater than the best so far, record the row and the sum.
- Return
[bestRow, bestCount].
Why it works
A strict comparison keeps the first row encountered among ties, which is the smallest index.
Complexity
- Time —
O(m · n) - Space —
O(1)
Pitfalls
- Initialise the best count to -1 so a matrix of all zeros returns row 0 with count 0.
Reference solution
Python
def rowAndMaximumOnes(mat):
best_row, best_count = 0, -1
for r, row in enumerate(mat):
count = sum(row)
if count > best_count:
best_count = count
best_row = r
return [best_row, best_count]Java
public static int[] rowAndMaximumOnes(int[][] mat) {
int bestRow = 0, bestCount = -1;
for (int r = 0; r < mat.length; r++) {
int count = 0;
for (int c = 0; c < mat[r].length; c++) count += mat[r][c];
if (count > bestCount) {
bestCount = count;
bestRow = r;
}
}
return new int[]{bestRow, bestCount};
}C++
vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
int bestRow = 0, bestCount = -1;
for (int r = 0; r < (int) mat.size(); r++) {
int count = 0;
for (int v : mat[r]) count += v;
if (count > bestCount) {
bestCount = count;
bestRow = r;
}
}
return {bestRow, bestCount};
}JavaScript
var rowAndMaximumOnes = function(mat) {
let bestRow = 0, bestCount = -1;
for (let r = 0; r < mat.length; r++) {
let count = 0;
for (let c = 0; c < mat[r].length; c++) count += mat[r][c];
if (count > bestCount) {
bestCount = count;
bestRow = r;
}
}
return [bestRow, bestCount];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal