How do I approach the Row With Maximum Ones problem?

Start by iterating through each row of the matrix and counting the ones in each row. Track the row with the highest count, and if counts are equal, return the smallest indexed row.

What is the time complexity of the solution?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns, due to the need to iterate over each element in the matrix.

How do I handle multiple rows with the same count of ones?

Simply track the smallest index of the row with the maximum number of ones. If two rows have the same count, return the row with the smaller index.

What if the matrix is empty or contains only zeros?

Even in these cases, the algorithm should return the first row with zero ones. Handle edge cases like these to ensure robustness.

How can I improve the efficiency of the algorithm?

Ensure that you stop iterating over rows early if possible, and avoid unnecessary recalculations. Using a more advanced approach like binary search might speed up counting ones in sorted rows.

#2643

Easy

auto_awesome数组·matrix

LeetCode 题解工作台

一最多的行

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。如果有多行包含最多的 1 ，只需要选择行下标最小的那一行。返回一个由行下标和该行中 1 的数量组成的数组。示例 1：输入： mat = [[0,1],[1,0]]…

数组矩阵

题目描述

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。

如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。

返回一个由行下标和该行中 1 的数量组成的数组。

示例 1：

输入：mat = [[0,1],[1,0]]
输出：[0,1]
解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。

示例 2：

输入：mat = [[0,0,0],[0,1,1]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

示例 3：

输入：mat = [[0,0],[1,1],[0,0]]
输出：[1,2]
解释：下标为 1 的行中 1 的数量最多。该行 1 的数量为 2 。所以，答案为 [1,2] 。

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] 为 0 或 1

lightbulb

解题思路

方法一：模拟

我们初始化一个数组 $\textit{ans} = [0, 0]$ ，用于记录最多 $1$ 的行的下标和 $1$ 的数量。

然后遍历矩阵的每一行，对于每一行：

计算该行 $1$ 的数量 $\textit{cnt}$ （由于矩阵中只包含 $0$ 和 $1$ ，我们可以直接对该行求和）；
如果 $\textit{ans}[1] < \textit{cnt}$ ，则更新 $\textit{ans} = [i, \textit{cnt}]$ 。

遍历结束后，返回 $\textit{ans}$ 。

时间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's ability to work with matrix traversal and counting techniques.
question_mark
Checks if the candidate can identify the smallest index in the case of multiple maximum counts.
question_mark
Assesses how well the candidate manages efficiency for larger matrices.

warning

常见陷阱

外企场景

error
Not handling cases with multiple rows having the same number of ones correctly.
error
Failing to consider the matrix's size and making the solution inefficient for larger inputs.
error
Incorrectly implementing the count of ones or missing edge cases, such as an empty row or no ones in a row.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the matrix has only zeros? The algorithm should still return a valid row, even if all counts are zero.
arrow_right_alt
What if the matrix contains only one row or one column? Consider edge cases where the matrix is minimal.
arrow_right_alt
If we wanted to find the row with the least number of ones instead, how would that change the solution?

help

常见问题

外企场景

继续练习

#2639 查询网格图中每一列的宽度 #2658 网格图中鱼的最大数目 #2661 找出叠涂元素