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.
For example:
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 maximum count of ones (1).
mat = [[0,0,0],[0,1,1]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So we return its index, 1, and the count.
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].
What is the optimal solution?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to finding the row with the most ones involves checking each row individually. We will count the number of ones in each row and then compare the counts to find the maximum.
Here's how the algorithm would work step-by-step:
def row_with_maximum_ones_brute_force(matrix):
max_ones_count = 0
row_with_max_ones = -1
# Iterate through each row of the matrix
for row_index in range(len(matrix)):
current_ones_count = 0
# Count ones in current row.
for element in matrix[row_index]:
if element == 1:
current_ones_count += 1
# Update row with max ones if current row has more ones
if current_ones_count > max_ones_count:
max_ones_count = current_ones_count
row_with_max_ones = row_index
return row_with_max_ones
To efficiently find the row with the most ones, we avoid checking every single element. We use a process of elimination, starting from the top right and strategically moving either down or left to quickly identify the target row.
Here's how the algorithm would work step-by-step:
def row_with_max_ones(matrix):
number_of_rows = len(matrix)
number_of_columns = len(matrix[0]) if number_of_rows > 0 else 0
row_index = 0
column_index = number_of_columns - 1
row_with_max_ones_index = -1
while row_index < number_of_rows and column_index >= 0:
if matrix[row_index][column_index] == 1:
# Found a one, so update the row index with max ones
row_with_max_ones_index = row_index
# Move left to find more ones in the matrix
column_index -= 1
else:
# Current element is 0, move to the next row
row_index += 1
# Moving down, so ones may still exist.
return row_with_max_ones_index
Case | How to Handle |
---|---|
Null or empty input matrix | Return -1 immediately as there are no rows to analyze. |
Matrix with zero rows or zero columns | Return -1 if the number of rows is zero, or 0 if number of columns is zero with at least one row. |
Matrix with only one row | Iterate through the row and count the ones; if ones exist, return 0; else return -1. |
Matrix with all zeros | Return 0 (or -1 if explicitly required) as the first row will have the maximum (zero) number of ones. |
Matrix with all ones | Return 0 as the first row will trivially have the maximum number of ones (equal to number of columns). |
Matrix where all rows have the same number of ones | Return the index of the first row (0), as specified by the implicit 'first occurrence' requirement. |
Very large matrix (potential for integer overflow during counting) | Use a 64-bit integer type (long) for counting ones to prevent overflow. |
Matrix with negative numbers (if allowed by the problem) | Handle the negative numbers gracefully, likely skipping them as they are not considered 'ones', unless problem states otherwise. |