Row With Maximum Ones - Solution & Explanation

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.