Find Row with Maximum Number of 1’s

Understanding the Problem

The goal is to find the row in a binary matrix that contains the maximum number of 1's.

Method 1: Simple Iteration

This method iterates through each row and counts the number of 1's.

def find_row_with_max_ones(matrix):
    max_row_index = -1
    max_count = 0

    for i in range(len(matrix)):
        count = sum(matrix[i])  # Count the number of 1's in the row
        if count > max_count:
            max_count = count
            max_row_index = i
    return max_row_index

# Example usage
matrix = [
    [0, 0, 1, 1],
    [1, 1, 1, 1],
    [0, 0, 0, 0],
    [1, 1, 0, 0]
]
result = find_row_with_max_ones(matrix)
print("Row with maximum number of 1's:", result)
            

Output:

Row with maximum number of 1's: 1

Method 2: Using Binary Search

This method assumes each row is sorted and uses binary search to find the first 1.

def binary_search(row):
    low, high = 0, len(row) - 1
    while low <= high:
        mid = (low + high) // 2
        if row[mid] == 1:
            if mid == 0 or row[mid - 1] == 0:
                return mid  # First occurrence of 1
            high = mid - 1
        else:
            low = mid + 1
    return -1  # No 1 found

def find_row_with_max_ones(matrix):
    max_row_index = -1
    max_count = 0

    for i in range(len(matrix)):
        index = binary_search(matrix[i])
        if index != -1:
            count = len(matrix[i]) - index  # Count of 1's
            if count > max_count:
                max_count = count
                max_row_index = i
    return max_row_index

# Example usage
matrix = [
    [0, 0, 1, 1],
    [1, 1, 1, 1],
    [0, 0, 0, 0],
    [1, 1, 0, 0]
]
result = find_row_with_max_ones(matrix)
print("Row with maximum number of 1's:", result)
            

Output:

Row with maximum number of 1's: 1

Method 3: Using Two-Pointer Technique

This method uses a two-pointer technique to find the row with the maximum number of 1's.

def find_row_with_max_ones(matrix):
    max_row_index = 0
    max_count = 0
    j = len(matrix[0]) - 1  # Start from the last column

    for i in range(len(matrix)):
        while j >= 0 and matrix[i][j] == 1:
            j -= 1  # Move left
        count = len(matrix[i]) - 1 - j  # Count of 1's in the current row
        if count > max_count:
            max_count = count
            max_row_index = i
    return max_row_index

# Example usage
matrix = [
    [0, 0, 1, 1],
    [1, 1, 1, 1],
    [0, 0, 0, 0],
    [1, 1, 0, 0]
]
result = find_row_with_max_ones(matrix)
print("Row with maximum number of 1's:", result)
            

Output:

Row with maximum number of 1's: 1