Maximum Ones Row - C++ Solution

1. Introduction

This blog post addresses a matrix traversal problem in a binary, row-wise sorted matrix. The challenge is to find the row with the maximum number of 1’s in linear time. This is an interesting problem as it combines the concepts of matrix traversal and optimization.

Problem

Given a binary M × N matrix where each row is sorted, we need to find the row that contains the maximum number of 1’s. The solution should be efficient, ideally linear in time. If multiple rows have the same maximum number of 1’s, return the first such row. If no 1’s are present, return 0.

2. Solution Steps

1. Start from the top-right corner of the matrix.

2. Move left if the current element is 1 and down if it is 0.

3. Keep track of the row with the maximum number of 1's.

4. Continue this process until you traverse all rows.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the row with maximum number of 1's
int findMaxOnesRow(const vector<vector<int>>& matrix) {
    int maxRow = 0, maxCount = 0;
    int row = 0, col = matrix[0].size() - 1;

    while (row < matrix.size() && col >= 0) {
        if (matrix[row][col] == 1) {
            int count = col + 1;
            if (count > maxCount) {
                maxCount = count;
                maxRow = row;
            }
            col--;
        } else {
            row++;
        }
    }

    return (maxCount > 0) ? maxRow + 1 : 0;
}

int main() {
    vector<vector<int>> matrix = {
        {0, 0, 0, 1, 1},
        // ... (other rows)
    };

    cout << "Row with maximum 1's: " << findMaxOnesRow(matrix) << endl;
    return 0;
}

Output:

Row with maximum 1's: 4

Explanation:

The function findMaxOnesRow finds the row with the maximum number of 1's in a binary matrix, where each row is sorted. It starts from the top-right corner and moves leftward for 1's and downward for 0's, efficiently finding the row with the most 1's. For the given matrix, row 4 contains the maximum number of 1's. The function also handles cases where multiple rows have the same number of 1's, returning the first such row, or returning 0 if no 1's are present.