Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. In a sorted 0/1 row, the number of 1s is m − (index of the first 1).
  2. 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);
    }
}

Solve Row with Maximum 1s online · All practice problems