Row with Maximum Number of 1's

Given a binary matrix of size n x m, where each row is sorted (0s appear before 1s), your task is to find the index of the row that contains the maximum number of 1's.

• If multiple rows have the same number of 1's, return the index of the first such row.
• If the matrix is empty or contains no 1's at all, return -1.

Understanding the Problem

We are given a binary matrix where each row is sorted in non-decreasing order — that means all 0s come before any 1s in every row. Our task is to find the index of the row that contains the maximum number of 1's.

If multiple rows have the same highest number of 1’s, we must return the first such row (the one with the smallest index). If the matrix is empty or has no 1’s at all, we return -1.

Since rows are sorted, this opens the door for a faster approach than simply scanning each cell — we can use binary search to find the first 1 in each row and calculate the count of 1s from there.

Step-by-Step Solution with Example

Step 1: Take a sample input

matrix = [
  [0, 0, 1, 1],
  [0, 1, 1, 1],
  [0, 0, 0, 1]
]

This matrix has 3 rows. Each row is sorted.

Step 2: Use binary search on each row

For each row, we perform binary search to find the first occurrence of 1. Since the row is sorted, once we know where 1s begin, we can count the number of 1s as number_of_1s = total_columns - index_of_first_1.

Step 3: Go row by row

• Row 0: Binary search gives first 1 at index 2 → 2 ones
• Row 1: First 1 at index 1 → 3 ones
• Row 2: First 1 at index 3 → 1 one

Row 1 has the most 1s. So, the answer is 1.

Step 4: Keep track of max count and row index

As we process each row, we store the max count of 1s found so far and update the result row index if we find a row with more 1s.

Edge Cases

• Matrix is empty: Return -1
• All elements are 0: No 1s found → Return -1
• All rows have same number of 1s: Return index of the first such row
• First row is full of 1s: We can stop early because no other row can have more 1s

Finally

This problem becomes much simpler once we realize that rows are sorted. Using binary search for each row significantly speeds up our solution compared to brute-force scanning. This solution works efficiently even for large matrices with a time complexity of O(n log m), where n is the number of rows and m is the number of columns.

For beginners, always look for problem constraints (like sorted rows) that you can exploit using optimized techniques like binary search.

1. Initialize maxOnesRow = -1 and maxOnes = 0.
2. For each row, do binary search to find the index of first 1.
3. If number of 1s in the row = m - index_of_first_1 is more than maxOnes, update both maxOnes and maxOnesRow.
4. After checking all rows, return maxOnesRow.

#include <stdio.h>

int findFirstOne(int row[], int m) {
    int low = 0, high = m - 1, index = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (row[mid] == 1) {
            index = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return index;
}

int rowWithMaxOnes(int matrix[][4], int n, int m) {
    int maxRow = -1, maxOnes = 0;
    for (int i = 0; i < n; i++) {
        int first = findFirstOne(matrix[i], m);
        if (first != -1 && m - first > maxOnes) {
            maxOnes = m - first;
            maxRow = i;
        }
    }
    return maxRow;
}

int main() {
    int matrix[3][4] = {{0, 0, 1, 1}, {0, 1, 1, 1}, {0, 0, 0, 1}};
    printf("Row with max 1's: %d\n", rowWithMaxOnes(matrix, 3, 4));
    return 0;
}

#include <iostream>
using namespace std;

int findFirstOne(int row[], int m) {
    int low = 0, high = m - 1, index = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (row[mid] == 1) {
            index = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return index;
}

int rowWithMaxOnes(int matrix[][4], int n, int m) {
    int maxRow = -1, maxOnes = 0;
    for (int i = 0; i < n; i++) {
        int first = findFirstOne(matrix[i], m);
        if (first != -1 && m - first > maxOnes) {
            maxOnes = m - first;
            maxRow = i;
        }
    }
    return maxRow;
}

int main() {
    int matrix[3][4] = {{0, 0, 1, 1}, {0, 1, 1, 1}, {0, 0, 0, 1}};
    cout << "Row with max 1's: " << rowWithMaxOnes(matrix, 3, 4) << endl;
    return 0;
}

def find_first_one(row):
    low, high = 0, len(row) - 1
    index = -1
    while low <= high:
        mid = (low + high) // 2
        if row[mid] == 1:
            index = mid
            high = mid - 1
        else:
            low = mid + 1
    return index

def row_with_max_ones(matrix):
    max_row = -1
    max_ones = 0
    for i, row in enumerate(matrix):
        first = find_first_one(row)
        if first != -1:
            ones = len(row) - first
            if ones > max_ones:
                max_ones = ones
                max_row = i
    return max_row

matrix = [[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1]]
print("Row with max 1's:", row_with_max_ones(matrix))

public class MaxOnesRowFinder {
  public static int rowWithMaxOnes(int[][] matrix) {
    int n = matrix.length, m = matrix[0].length;
    int maxRow = -1, maxOnes = 0;
    for (int i = 0; i < n; i++) {
      int first = findFirstOne(matrix[i], m);
      if (first != -1) {
        int ones = m - first;
        if (ones > maxOnes) {
          maxOnes = ones;
          maxRow = i;
        }
      }
    }
    return maxRow;
  }

  private static int findFirstOne(int[] row, int m) {
    int low = 0, high = m - 1, index = -1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (row[mid] == 1) {
        index = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return index;
  }

  public static void main(String[] args) {
    int[][] matrix = {
      {0, 0, 1, 1},
      {0, 1, 1, 1},
      {0, 0, 0, 1}
    };
    System.out.println("Row with max 1's: " + rowWithMaxOnes(matrix));
  }
}

function findFirstOne(row) {
  let low = 0, high = row.length - 1, index = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (row[mid] === 1) {
      index = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return index;
}

function rowWithMaxOnes(matrix) {
  let maxOnes = 0, maxRow = -1;
  for (let i = 0; i < matrix.length; i++) {
    let first = findFirstOne(matrix[i]);
    if (first !== -1) {
      let count = matrix[0].length - first;
      if (count > maxOnes) {
        maxOnes = count;
        maxRow = i;
      }
    }
  }
  return maxRow;
}

const matrix = [[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1]];
console.log("Row with max 1's:", rowWithMaxOnes(matrix));

package main
import "fmt"

func findFirstOne(row []int) int {
    low, high := 0, len(row)-1
    index := -1
    for low <= high {
        mid := (low + high) / 2
        if row[mid] == 1 {
            index = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return index
}

func rowWithMaxOnes(matrix [][]int) int {
    maxRow := -1
    maxOnes := 0
    for i, row := range matrix {
        first := findFirstOne(row)
        if first != -1 {
            ones := len(row) - first
            if ones > maxOnes {
                maxOnes = ones
                maxRow = i
            }
        }
    }
    return maxRow
}

func main() {
    matrix := [][]int{
        {0, 0, 1, 1},
        {0, 1, 1, 1},
        {0, 0, 0, 1},
    }
    fmt.Println("Row with max 1's:", rowWithMaxOnes(matrix))
}

fn find_first_one(row: &Vec<i32>) -> Option<usize> {
    let (mut low, mut high) = (0, row.len() - 1);
    let mut index = None;
    while low <= high {
        let mid = (low + high) / 2;
        if row[mid] == 1 {
            index = Some(mid);
            if mid == 0 { break; }
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    index
}

fn row_with_max_ones(matrix: Vec<Vec<i32>>) -> i32 {
    let mut max_row = -1;
    let mut max_ones = 0;
    for (i, row) in matrix.iter().enumerate() {
        if let Some(first) = find_first_one(row) {
            let ones = row.len() - first;
            if ones > max_ones {
                max_ones = ones;
                max_row = i as i32;
            }
        }
    }
    max_row
}

fn main() {
    let matrix = vec![
        vec![0, 0, 1, 1],
        vec![0, 1, 1, 1],
        vec![0, 0, 0, 1],
    ];
    println!("Row with max 1's: {}", row_with_max_ones(matrix));
}

fun findFirstOne(row: List<Int>): Int {
    var low = 0
    var high = row.size - 1
    var index = -1
    while (low <= high) {
        val mid = (low + high) / 2
        if (row[mid] == 1) {
            index = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return index
}

fun rowWithMaxOnes(matrix: List<List<Int>>): Int {
    var maxRow = -1
    var maxOnes = 0
    for ((i, row) in matrix.withIndex()) {
        val first = findFirstOne(row)
        if (first != -1) {
            val ones = row.size - first
            if (ones > maxOnes) {
                maxOnes = ones
                maxRow = i
            }
        }
    }
    return maxRow
}

fun main() {
    val matrix = listOf(
        listOf(0, 0, 1, 1),
        listOf(0, 1, 1, 1),
        listOf(0, 0, 0, 1)
    )
    println("Row with max 1's: ${rowWithMaxOnes(matrix)}")
}

func findFirstOne(_ row: [Int]) -> Int? {
    var low = 0, high = row.count - 1
    var index: Int? = nil
    while low <= high {
        let mid = (low + high) / 2
        if row[mid] == 1 {
            index = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return index
}

func rowWithMaxOnes(_ matrix: [[Int]]) -> Int {
    var maxRow = -1
    var maxOnes = 0
    for (i, row) in matrix.enumerated() {
        if let first = findFirstOne(row) {
            let ones = row.count - first
            if ones > maxOnes {
                maxOnes = ones
                maxRow = i
            }
        }
    }
    return maxRow
}

let matrix = [[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1]]
print("Row with max 1's:", rowWithMaxOnes(matrix))

function findFirstOne(row: number[]): number {
  let low = 0, high = row.length - 1, index = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (row[mid] === 1) {
      index = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return index;
}

function rowWithMaxOnes(matrix: number[][]): number {
  let maxRow = -1, maxOnes = 0;
  for (let i = 0; i < matrix.length; i++) {
    let first = findFirstOne(matrix[i]);
    if (first !== -1) {
      let ones = matrix[i].length - first;
      if (ones > maxOnes) {
        maxOnes = ones;
        maxRow = i;
      }
    }
  }
  return maxRow;
}

const matrix: number[][] = [[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1]];
console.log("Row with max 1's:", rowWithMaxOnes(matrix));

Time complexity

Space complexity

O(1)

No extra space used other than a few variables.