Row With Maximum Ones

Easy

Amazon

1 view

Topics:

Arrays

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.

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 maximum count of ones (1). So, the answer is [0,1].

Example 2:

Input: 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. So, the answer is [1,2].

Example 3:

Input: 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].

Constraints:

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

Row With Maximum Ones

Easy

Amazon

1 view

Topics:

Arrays

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.

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 maximum count of ones (1). So, the answer is [0,1].

Example 2:

Input: 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. So, the answer is [1,2].

Example 3:

Input: 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].

Constraints:

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

Solution

Clarifying Questions

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:

What are the dimensions of the 2D array? Specifically, what are the maximum possible values for the number of rows and columns?
Is it guaranteed that all rows will have the same number of columns?
Can the input array be empty or contain null rows?
What should I return if multiple rows have the same maximum number of 1s? Should I return the first such row, or is there another tie-breaking condition?
Is the input array guaranteed to only contain 0s and 1s, or can it contain other integer values?

Brute Force Solution

Approach

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:

Start by examining the first row.
Count how many ones are in that row.
Remember this count and the row number.
Move to the next row and count the number of ones in that row.
Compare the number of ones in this row with the count you remembered.
If the current row has more ones, update the remembered count and row number.
Repeat this process for every row.
After checking all rows, the row number you remembered is the row with the most ones.

Code Implementation

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

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each row of the 2D array. Let 'm' be the number of rows and 'n' be the number of columns in the array. For each row, the algorithm counts the number of ones, which involves iterating through each element in that row. Therefore, for each of the 'm' rows, we perform 'n' operations to count the ones. The total number of operations is proportional to m*n, resulting in a time complexity of O(m*n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space to store the count of ones in the current row and the row number with the maximum ones found so far. These variables do not scale with the input size N (number of rows and columns in the matrix). Therefore, the auxiliary space complexity is O(1), indicating constant space usage irrespective of the input matrix dimensions.

Optimal Solution

Approach

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:

Begin looking at the top-right corner of the entire grid.
If you find a one, it means all rows above this one in the current column also cannot be the row with the most ones. Move to the left in the same row.
If you find a zero, it means the rows below this one *could* have more ones. Move down to the next row.
Keep going until you reach the left edge of the grid or the bottom of the grid.
The row where you last saw a one is the row with the highest number of ones.

Code Implementation

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

Big(O) Analysis

Time Complexity

O(m + n) – The algorithm starts at the top-right corner of the m x n matrix and moves either left or down in each step. In the worst-case scenario, it traverses all columns of the first row (n columns) and all rows of the last column (m rows). Therefore, the time complexity is proportional to the sum of the number of rows (m) and columns (n), resulting in O(m + n).

Space Complexity

O(1) – The algorithm utilizes a constant amount of extra space. It only requires a few variables to store the current row and column indices and potentially the index of the row with the maximum ones encountered so far. The number of these variables is independent of the dimensions of the input grid, which we can define as N rows and M columns. Therefore, the auxiliary space complexity is O(1).

Edge Cases

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.