Find the Row Containing the Most 1s in a Binary Matrix

Medium15–20 min

Topics

ArrayMatrixBinary Search

Companies

AmazonMicrosoft

Given a binary matrix where every row is sorted — all 0s before all 1s — return the index of the row with the most 1s. If every row has zero 1s, return -1. A row's 1-count is fully determined by where its first 1 sits, so binary-search each row for that index instead of scanning it, for an O(m log n) solution.

Test Case 1:

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

Output:1

Explanation:Row 1 is all 1s — the most of any row.

Test Case 2:

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

Output:2

Explanation:Row 2 has four 1s, more than any other row.

Test Case 3:

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

Output:-1

Explanation:No row has any 1s at all.

Constraints

◆1 ≤ matrix.length, matrix[0].length ≤ 1000
◆Every value is 0 or 1
◆Every row is sorted — all 0s before all 1s

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

matrix (rows separated by ;, values 0/1) — 1-5 rows, 1-6 cols, each row sorted 0s then 1s

1	class Solution {
2	public int rowWithMax1s(int[][] matrix) {
3	int n = matrix[0].length;
4	int maxCount = 0, maxRow = -1;
5	for (int i = 0; i < matrix.length; i++) {
6	int lo = 0, hi = n - 1, firstOne = n;
7	while (lo <= hi) {
8	int mid = lo + (hi - lo) / 2;
9	if (matrix[i][mid] == 1) {
10	firstOne = mid;
11	hi = mid - 1;
12	} else {
13	lo = mid + 1;
14	}
15	}
16	int count = n - firstOne;
17	if (count > maxCount) {
18	maxCount = count;
19	maxRow = i;
20	}
21	}
22	return maxRow;
23	}
24	}
25

Variables

n3

maxCount0

maxRow-1

INITIALIZE

For each row, binary-search for the index of its first 1 (rows are sorted 0s then 1s) — the row's 1-count is n minus that index.

Step 1 / 8

Approach & Solutions

Brute Force — Count Every Cell

Brute

Count the 1s in every row with a plain scan and keep track of the best one. Correct regardless of how the row is arranged, but it never uses the fact that each row is sorted, which is what lets binary search find a row's count without checking every cell in it.

TimeO(m × n)

SpaceO(1)

Java

Try it out

class Solution {
    public int rowWithMax1s(int[][] matrix) {
        int maxCount = 0, maxRow = -1;
        for (int i = 0; i < matrix.length; i++) {
            int count = 0;
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 1) count++;
            }
            if (count > maxCount) {
                maxCount = count;
                maxRow = i;
            }
        }
        return maxRow;
    }
}

Optimal — Binary Search Each Row

Optimal

Each row is sorted 0s-then-1s, so a row's 1-count is completely determined by where its first 1 sits: count = n - firstOneIndex. Binary-search each row for that index (a lower bound of 1) instead of scanning it, and keep the row with the largest count.

TimeO(m log n)