LeetCode 2643 - Row With Maximum Ones

LeetCode Problem 2643

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Here is the complete, detailed technical solution guide for LeetCode 2643 - Row With Maximum Ones following your exact formatting requirements.

Problem Understanding

The problem presents a binary matrix mat of size m x n, where each element is either 0 or 1. The task is to identify the row that contains the maximum number of ones and return both the index of that row and the count of ones in it. If multiple rows have the same maximum count of ones, the row with the smallest index should be returned.

The input mat is a two-dimensional array, with mat[i][j] representing the element at the i-th row and j-th column. The output is a two-element array [row_index, count_of_ones].

The constraints are 1 <= m, n <= 100, which implies that the matrix is reasonably small and allows an O(m * n) solution without performance issues. Each row is guaranteed to have only 0s or 1s, which simplifies counting operations.

Important edge cases include matrices where multiple rows have the same number of ones, matrices with all zeros, and matrices with all ones. These cases ensure that the solution correctly handles tie-breaking and counts correctly.

Approaches

The most straightforward approach is a brute-force solution. For each row in the matrix, count the number of ones by iterating through every element. Maintain a record of the maximum count found and the row index where it occurs. If a row has the same count as the current maximum, we retain the row with the smaller index to satisfy the problem's tie-breaking condition. This approach is simple and guarantees correctness because it examines every element of the matrix.

A minor optimization is possible using Python's built-in sum() function or Go’s inner loop summation, which makes counting ones in a row faster but does not change the overall time complexity. Given the problem size, an O(m * n) solution is fully acceptable and effectively optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(1)	Iterate through each row and count ones
Optimal	O(m * n)	O(1)	Count ones row by row using built-in sum, track maximum and row index

Algorithm Walkthrough

1. Initialize two variables, max_count to -1 and row_index to -1. These variables will store the maximum number of ones found so far and the corresponding row index.
2. Iterate over each row in the matrix using a loop. Let the current row index be i.
3. Count the number of ones in the current row. In Python, this can be done with sum(mat[i]). In Go, iterate through each element and increment a counter when the element is 1.
4. Compare the current row's count of ones with max_count.
5. If the current count is greater than max_count, update max_count with the current count and set row_index to i.
6. If the current count equals max_count, do nothing because the row with the smaller index is preferred.
7. After checking all rows, return [row_index, max_count] in Python or []int{row_index, max_count} in Go.

Why it works:

This algorithm guarantees correctness because it examines every row and every element exactly once, ensuring that no ones are missed. The invariant maintained is that at any point in the iteration, max_count always stores the largest number of ones found so far and row_index corresponds to the earliest row achieving this count. This satisfies the requirement to return the row with the maximum ones and the smallest index in case of ties.

Python Solution

from typing import List

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

Implementation explanation:

The solution initializes max_count and row_index to sentinel values. It loops through the matrix with enumerate, counting ones in each row with sum(row). Whenever a new maximum is found, both variables are updated. The solution directly returns the results in the expected format. Using sum() simplifies counting and keeps the code concise.

Go Solution

func rowAndMaximumOnes(mat [][]int) []int {
    maxCount := -1
    rowIndex := -1
    
    for i, row := range mat {
        count := 0
        for _, val := range row {
            if val == 1 {
                count++
            }
        }
        if count > maxCount {
            maxCount = count
            rowIndex = i
        }
    }
    
    return []int{rowIndex, maxCount}
}

Go-specific notes:

In Go, we use range to iterate over rows and elements. A counter count accumulates ones in the row. Unlike Python, Go does not have a built-in sum for slices, so an explicit inner loop is necessary. Returning a slice with the results [rowIndex, maxCount] matches the required output format. Edge cases like empty slices are not relevant due to the problem constraints.

Worked Examples

Example 1: mat = [[0,1],[1,0]]

Step	i	row	count	max_count	row_index
1	0	[0,1]	1	-1 → 1	-1 → 0
2	1	[1,0]	1	1	0

Result: [0,1]

Example 2: mat = [[0,0,0],[0,1,1]]

Step	i	row	count	max_count	row_index
1	0	[0,0,0]	0	-1 → 0	-1 → 0
2	1	[0,1,1]	2	0 → 2	0 → 1

Result: [1,2]

Example 3: mat = [[0,0],[1,1],[0,0]]

Step	i	row	count	max_count	row_index
1	0	[0,0]	0	-1 → 0	-1 → 0
2	1	[1,1]	2	0 → 2	0 → 1
3	2	[0,0]	0	2	1

Result: [1,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Each element of the m x n matrix is visited exactly once to count ones.
Space	O(1)	Only a few integer variables are used, independent of input size.

The solution is efficient given the constraints. The nested iteration over rows and columns is unavoidable for counting, and no additional data structures are used.

Test Cases

# Provided examples
assert Solution().rowAndMaximumOnes([[0,1],[1,0]]) == [0,1] # tie-breaking by row index
assert Solution().rowAndMaximumOnes([[0,0,0],[0,1,1]]) == [1,2] # row with maximum ones
assert Solution().rowAndMaximumOnes([[0,0],[1,1],[0,0]]) == [1,2] # middle row has max ones

# Edge and boundary cases
assert Solution().rowAndMaximumOnes([[1]]) == [0,1] # single element 1
assert Solution().rowAndMaximumOnes([[0]]) == [0,0] # single element 0
assert Solution().rowAndMaximumOnes([[1,1,1],[1,1,1]]) == [0,3] # all rows have same ones
assert Solution().rowAndMaximumOnes([[0,0,0],[0,0,0]]) == [0,0] # all zeros
assert Solution().rowAndMaximumOnes([[1,0,1],[1,1,0],[0,1,1]]) == [1,2] # multiple rows with same max

Test	Why
[[0,1],[1,0]]	Validates tie-breaking by smallest row index
[[0,0,0],[0,1,1]]	Ensures algorithm finds row with maximum ones
[[0,0],[1,1],[0,0]]	Confirms middle row is correctly identified
[[1]]	Single-element matrix, simplest non-zero case
[[0]]