Row with maximum number of 1s in a Matrix

Given a binary matrix of size M x N where each row is sorted in non-decreasing order (i.e., all 1s appear after all 0s), find the row with the maximum number of 1s. If there are multiple rows with the same number of 1s, return the first such row.

Input/Output Examples

plaintext
Example 1:
Input:
matrix = [
    [0, 1, 1, 1],
    [0, 0, 1, 1],
    [1, 1, 1, 1],
    [0, 0, 0, 0]
]

Output: 2
Explanation: Row 2 has the most 1s (four 1s), which is greater than any other row.

Example 2:
Input:
matrix = [
    [0, 0, 0],
    [0, 1, 1],
    [0, 0, 1]
]

Output: 1
Explanation: Row 1 has the most 1s (two 1s), which is more than any other row.

Example 3:
Input:
matrix = [
    [0, 0],
    [0, 0]
]

Output: -1
Explanation: There are no 1s in the matrix, so the output is -1.

Approach to Find the Row with Maximum Number of 1s

  1. Start from the Top-Right Corner:
    • Begin searching from the top-right corner of the matrix. This is because moving left from a 1 gives another 1 (if any), and moving down from a 0 skips unnecessary 0s.
  2. Move Left for Maximum 1s in Each Row:
    • If the current element is 1, move left to count more 1s and keep track of the row index.
    • If the current element is 0, move down to the next row since all elements to the left will also be 0s in a sorted row.
  3. Stop at the Bottom of the Matrix:
    • Continue this process until all rows are processed or until you reach the left-most column.
  4. Return the Row with the Maximum Number of 1s:
    • Track the row with the left-most 1 (indicating the highest count of 1s) and return its index.

C++ Program to Find the Row with Maximum Number of 1s

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

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

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

    return maxRowIndex;
}

int main() {
    vector<vector<int>> matrix = {
        {0, 1, 1, 1},
        {0, 0, 1, 1},
        {1, 1, 1, 1},
        {0, 0, 0, 0}
    };

    int result = rowWithMaxOnes(matrix);
    cout << "Row with maximum number of 1s: " << result << endl;
    return 0;
}

Java Program to Find the Row with Maximum Number of 1s

java
public class RowWithMaxOnes {

    // Function to find the row with the maximum number of 1s
    public static int rowWithMaxOnes(int[][] matrix) {
        int maxRowIndex = -1;
        int row = 0, col = matrix[0].length - 1;

        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == 1) {
                maxRowIndex = row;
                col--;
            } else {
                row++;
            }
        }

        return maxRowIndex;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {0, 1, 1, 1},
            {0, 0, 1, 1},
            {1, 1, 1, 1},
            {0, 0, 0, 0}
        };

        int result = rowWithMaxOnes(matrix);
        System.out.println("Row with maximum number of 1s: " + result);
    }
}

Python Program to Find the Row with Maximum Number of 1s

python
# Function to find the row with the maximum number of 1s
def row_with_max_ones(matrix):
    max_row_index = -1
    row, col = 0, len(matrix[0]) - 1

    while row < len(matrix) and col >= 0:
        if matrix[row][col] == 1:
            max_row_index = row
            col -= 1
        else:
            row += 1

    return max_row_index

# Example usage
if __name__ == "__main__":
    matrix = [
        [0, 1, 1, 1],
        [0, 0, 1, 1],
        [1, 1, 1, 1],
        [0, 0, 0, 0]
    ]
    result = row_with_max_ones(matrix)
    print("Row with maximum number of 1s:", result)
  • Time Complexity: O(M + N) where M is the number of rows and N is the number of columns, as each row or column is visited at most once.
  • Space Complexity: O(1) since only a constant amount of extra space is used for variables, regardless of the matrix size.

DSA

6800

871

Related Articles