Practice › Binary Search
Row with Maximum 1s
Easy · Binary Search · Asked at Amazon, Microsoft, Samsung, TCS, Infosys
Every row of the binary matrix is sorted (all 0s, then all 1s). Print the 0-based index of the row with the most 1s. If several rows tie, print the smallest index. If no row has a 1, print -1.
Input
First line: n m. Next n lines: m values (0 or 1).
Output
The row index, or -1.
Constraints
- 1 ≤ n, m ≤ 1000
Binary search the first 1 in each row (O(n log m)), or walk a staircase from the top-right corner (O(n + m)).
Example 1
Input
3 4 0 1 1 1 0 0 1 1 1 1 1 1
Output
2
Example 2
Input
2 2 0 0 0 0
Output
-1
Hints
- In a sorted 0/1 row, the number of 1s is m − (index of the first 1).
- Staircase trick: start at the top-right corner. Move left while you see a 1 (that row beats all previous ones), otherwise move down.
Approach
Start at row 0, column m − 1. In each row, while the cell to the left of the current column is 1 (or the current cell is 1), move left and mark this row as the best — it has more 1s than any row before it. Then go to the next row. The column pointer only moves left and the row pointer only moves down, so the walk is O(n + m). Only strictly more 1s update the answer, so ties keep the smaller row index.
Complexity: O(n + m) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n, vector<int>(m));
for (auto &row : g)
for (auto &x : row) cin >> x;
int col = m, best = -1; // col = index of the leftmost 1 found so far
for (int i = 0; i < n; i++) {
while (col > 0 && g[i][col - 1] == 1) {
col--;
best = i;
}
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
g = [data[2 + i * m : 2 + (i + 1) * m] for i in range(n)]
col, best = m, -1
for i in range(n):
while col > 0 and g[i][col - 1] == 1:
col -= 1
best = i
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[][] g = new int[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) g[i][j] = sc.nextInt();
int col = m, best = -1;
for (int i = 0; i < n; i++) {
while (col > 0 && g[i][col - 1] == 1) {
col--;
best = i;
}
}
System.out.println(best);
}
}