Row With Maximum Ones

Difficulty: Easy | Acceptance: 74.30% | Paid: No Topics: Array, Matrix

Given a m x n binary matrix mat, return the 0-indexed position of the row that has the maximum number of 1’s. If there are multiple rows that have the maximum number of 1’s, return the smallest index.

• Examples
• Constraints
• Linear Scan
• Built-in Sum Functions

Examples

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 count of 1’s, 1.

Example 2:

Input: mat = [[0,0,0],[0,1,1]] Output: [1,2] Explanation: The second row has two 1’s which is greater than the first row’s zero 1’s.

Example 3:

Input: mat = [[0,0],[1,1],[0,0]] Output: [1,2] Explanation: The second row has two 1’s which is the maximum.

Constraints

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

Linear Scan

Intuition We iterate through each row of the matrix, count the number of 1s manually, and keep track of the row with the maximum count found so far.

Steps

• Initialize maxOnes to -1 and maxIndex to 0.
• Iterate through each row i from 0 to m-1.
• For each row, iterate through each element j from 0 to n-1.
• If the element is 1, increment a local count variable.
• After finishing the inner loop, compare count with maxOnes.
• If count > maxOnes, update maxOnes to count and maxIndex to i.
• Return [maxIndex, maxOnes].

class Solution:
    def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
        max_ones = -1
        max_idx = 0
        for i in range(len(mat)):
            count = 0
            for val in mat[i]:
                if val == 1:
                    count += 1
            if count > max_ones:
                max_ones = count
                max_idx = i
        return [max_idx, max_ones]

Complexity

• Time: O(m × n) — We visit every element in the matrix exactly once.
• Space: O(1) — We only use a few variables for counting and tracking the maximum.
• Notes: This is the most fundamental approach and works well given the constraints (matrix size up to 100x100).

Built-in Sum Functions

Intuition Most programming languages provide built-in functions to sum the elements of an array or list. We can leverage these to make the code cleaner and more concise by replacing the inner loop with a sum function.

Steps

• Initialize maxOnes to -1 and maxIndex to 0.
• Iterate through each row i in the matrix.
• Use the language’s built-in sum function to calculate the total 1s in the current row.
• Compare this sum with maxOnes.
• If the sum is greater, update maxOnes and maxIndex.
• Return [maxIndex, maxOnes].

class Solution:
    def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
        max_ones = -1
        max_idx = 0
        for i, row in enumerate(mat):
            count = sum(row)
            if count > max_ones:
                max_ones = count
                max_idx = i
        return [max_idx, max_ones]

Complexity

• Time: O(m × n) — The built-in sum functions still iterate through each element of the row internally.
• Space: O(1) — No extra space proportional to input size is used.
• Notes: This approach improves code readability and maintainability by using standard library functions, though the asymptotic complexity remains the same.