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.

#include <iostream>
using namespace std;

int findRowWithMaxOnes(int matrix[][100], int rows, int cols) {
    int maxRowIndex = -1;
    int maxCount = 0;

    for (int i = 0; i < rows; i++) {
        int count = 0;
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 1) {
                count++;
            }
        }
        if (count > maxCount) {
            maxCount = count;
            maxRowIndex = i;
        }
    }
    return maxRowIndex;
}

int main() {
    int matrix[100][100] = {
        {0, 0, 1, 1},
        {1, 1, 1, 1},
        {0, 0, 0, 0},
        {1, 1, 0, 0}
    };
    int rows = 4, cols = 4;
    int result = findRowWithMaxOnes(matrix, rows, cols);
    cout << "Row with maximum number of 1's: " << result << endl;
    return 0;
}
            

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.

#include <iostream>
using namespace std;

int binarySearch(int row[], int cols) {
    int low = 0, high = cols - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (row[mid] == 1) {
            if (mid == 0 || row[mid - 1] == 0) {
                return mid; // First occurrence of 1
            }
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1; // No 1 found
}

int findRowWithMaxOnes(int matrix[][100], int rows, int cols) {
    int maxRowIndex = -1;
    int maxCount = 0;

    for (int i = 0; i < rows; i++) {
        int index = binarySearch(matrix[i], cols);
        if (index != -1) {
            int count = cols - index; // Count of 1's
            if (count > maxCount) {
                maxCount = count;
                maxRowIndex = i;
            }
        }
    }
    return maxRowIndex;
}

int main() {
    int matrix[100][100] = {
        {0, 0, 1, 1},
        {1, 1, 1, 1},
        {0, 0, 0, 0},
        {1, 1, 0, 0}
    };
    int rows = 4, cols = 4;
    int result = findRowWithMaxOnes(matrix, rows, cols);
    cout << "Row with maximum number of 1's: " << result << endl;
    return 0;
}
            

Output:

Row with maximum number of 1's: 1

Explanation:

The binary search method is efficient for sorted rows (O(m log n) time complexity):

• Performs binary search on each row to find the first occurrence of 1
• Calculates the count of 1's by subtracting the index from column count
• Tracks the row with maximum 1's count

This method is optimal when rows are already sorted.

Method 3: Using Two-Pointer Technique

This method uses a two-pointer approach for optimal O(m+n) time complexity.

#include <iostream>
using namespace std;

int findRowWithMaxOnes(int matrix[][100], int rows, int cols) {
    int maxRowIndex = 0;
    int maxCount = 0;
    int j = cols - 1; // Start from last column

    for (int i = 0; i < rows; i++) {
        // Move left until we find 0 or reach start
        while (j >= 0 && matrix[i][j] == 1) {
            j--;
        }
        // Calculate number of 1's
        int currentCount = cols - 1 - j;
        // Update max if current row has more 1's
        if (currentCount > maxCount) {
            maxCount = currentCount;
            maxRowIndex = i;
        }
    }
    return maxRowIndex;
}

int main() {
    int matrix[100][100] = {
        {0, 0, 1, 1},
        {1, 1, 1, 1},
        {0, 0, 0, 0},
        {1, 1, 0, 0}
    };
    int rows = 4, cols = 4;
    int result = findRowWithMaxOnes(matrix, rows, cols);
    cout << "Row with maximum number of 1's: " << result << endl;
    return 0;
}
            

Output:

Row with maximum number of 1's: 1

Explanation:

The two-pointer technique provides the most efficient solution (O(m+n)):

• Starts from the top-right corner of the matrix
• Moves left when encountering 1's (to find first 0)
• Moves down when encountering 0's
• Keeps track of the row with maximum 1's

This method works best for large matrices with sorted rows.