We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Row With Maximum Ones

Number: 2737

Difficulty: Easy

Paid? No

Companies: Amazon, Google

Problem Description

Given a binary matrix where each element is either 0 or 1, determine the row that contains the maximum number of ones. In the case of a tie (multiple rows having the same number of ones), select the row with the smallest index. Return an array containing the index of that row and the count of ones in it.

Key Insights

  • Iterate through each row of the matrix.
  • Count the number of ones in each row.
  • Keep track of the row with the highest count of ones.
  • In case of a tie, prefer the row with the smaller index.
  • The approach involves a simple traversal leading to O(m * n) time complexity.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(1) additional space is used.

Solution

The solution iterates through the matrix row by row, counting the number of ones in each row. As it processes each row, it updates the maximum count and index if the current row has a higher count than previously seen. If the count is equal to the maximum, the smallest row index is naturally maintained since rows are processed in order. This straightforward algorithm efficiently finds the answer by scanning through the matrix only once.

Code Solutions

# Python solution for Row With Maximum Ones

def rowWithMaxOnes(mat):
    # Initialize variables to store the index of the row with the maximum ones and the count
    max_row_index = 0
    max_count = 0
    
    # Iterate through each row and its index in the matrix
    for i, row in enumerate(mat):
        # Count the number of ones in the current row
        current_count = sum(row)
        # Update if the current row has more ones than the current maximum
        if current_count > max_count:
            max_count = current_count
            max_row_index = i
    # Return the row index along with its count of ones
    return [max_row_index, max_count]

# Example usage:
# print(rowWithMaxOnes([[0, 1], [1, 0]]))
← Back to All Questions