Row With Maximum Ones
EasyPrompt
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:
)Example 2:
(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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses an auxiliary array to store the count of ones for each row. It first populates this array by iterating through the matrix, and then performs a second pass over the auxiliary array to find the row with the maximum number of ones.
Algorithm
- Create an integer array
ones_countsof sizem(number of rows). - Iterate through the matrix from row
i = 0tom-1. - For each row
i, count the number of1s and store the result inones_counts[i]. - Initialize
max_count = -1andresult_index = -1. - Iterate through
ones_countsfromi = 0tom-1. - If
ones_counts[i]is greater thanmax_count, updatemax_counttoones_counts[i]andresult_indextoi. - Return
[result_index, max_count].
Walkthrough
The core idea is to separate the problem into two distinct phases: counting and finding the maximum.
First, we create an array, let's call it ones_counts, with the same number of elements as there are rows in the matrix. We then iterate through each row of the input matrix mat, count the number of 1s, and store this count in the corresponding index of our ones_counts array.
After the first phase, ones_counts[i] will hold the number of ones in mat[i]. In the second phase, we simply iterate through the ones_counts array to find the maximum value. We keep track of the maximum count found so far and the index at which it occurred. The first time we encounter the maximum value, we record its index. Due to the tie-breaking rule (smallest row number), we don't update the index if we find another row with the same maximum count.
class Solution { public int[] rowAndMaximumOnes(int[][] mat) { int m = mat.length; int n = mat[0].length; int[] onesCounts = new int[m]; for (int i = 0; i < m; i++) { int count = 0; for (int j = 0; j < n; j++) { if (mat[i][j] == 1) { count++; } } onesCounts[i] = count; } int maxOnes = -1; int rowIndex = -1; for (int i = 0; i < m; i++) { if (onesCounts[i] > maxOnes) { maxOnes = onesCounts[i]; rowIndex = i; } } return new int[]{rowIndex, maxOnes}; }}Complexity
Time
O(m * n), where `m` is the number of rows and `n` is the number of columns. The first pass to count ones takes O(m * n) time, and the second pass to find the maximum takes O(m) time. The total time complexity is dominated by the first pass.
Space
O(m), as an auxiliary array of size `m` is used to store the count of ones for each row.
Trade-offs
Pros
The logic is clearly separated into two steps: counting and finding the maximum, which might be easier to reason about.
The code is straightforward to write and understand.
Cons
It uses extra space of O(m), where m is the number of rows. This is inefficient compared to a constant space solution.
It requires two passes over the rows (one to populate the counts array, one to find the max), which is less performant than a single-pass solution.
Solutions
Solution
public class Solution { public int[] RowAndMaximumOnes(int[][] mat) { int[] ans = new int[2]; for (int i = 0; i < mat.Length; i++) { int cnt = mat[i].Sum(); if (ans[1] < cnt) { ans = new int[] { i, cnt }; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.