Row with max 1s

Medium Binary Search 2D Binary Search + Step Search Original on GeeksforGeeks

Row with max 1s is a medium binary search problem solved with the 2d binary search + step search pattern. The best approach, optimal (staircase from the top-right), runs in O(n + m) time and O(1) space. Below are 2 approaches in Java, from binary search each row up.

Problem

In a binary matrix where every row is sorted (0s then 1s), return the index of the first row with the most 1s, or -1 if the matrix has no 1s.

Examples

Example 1

Input: arr = [[0,1,1,1],[0,0,1,1],[1,1,1,1],[0,0,0,0]]
Output: 2
Why: Row 2 has four 1s.

Example 2

Input: arr = [[0,0],[0,0]]
Output: -1

Constraints

1 <= n, m <= 10^3
Each row is sorted: all 0s, then all 1s.
Return the first row with the most 1s, or -1 if there are none.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Binary search each row	`O(n log m)`	`O(1)`
Optimal (staircase from the top-right)	`O(n + m)`	`O(1)`

1Binary search each row

TimeO(n log m)

SpaceO(1)

In each sorted row, bisect_left(1) gives the first 1, so the row has m - index ones.

For each row, binary search the first 1.
Keep the row with the largest count (first on ties).

Java

class Solution {
    public int rowWithMax1s(int[][] arr) {
        int m = arr[0].length, best = -1, bestCount = 0;
        for (int r = 0; r < arr.length; r++) {
            int lo = 0, hi = m;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (arr[r][mid] == 1) hi = mid; else lo = mid + 1;
            }
            if (m - lo > bestCount) { bestCount = m - lo; best = r; }
        }
        return best;
    }
}

2Optimal (staircase from the top-right)

TimeO(n + m)c moves left at most m times; r moves down n times.

SpaceO(1)

Keep a column pointer c starting at the last column. In each row, move c left while arr[r][c] == 1; each move means this row beats every row before it. The pointer only ever moves left.

c = m - 1, best = -1.
For each row r: while c >= 0 and arr[r][c] == 1: c--, best = r.
Return best.

Java

class Solution {
    public int rowWithMax1s(int[][] arr) {
        int c = arr[0].length - 1, best = -1;
        for (int r = 0; r < arr.length; r++) {
            while (c >= 0 && arr[r][c] == 1) {
                c--;
                best = r;
            }
        }
        return best;
    }
}

Edge cases to test

No 1s anywhere
Ties (return the smaller row index)

Hints

Hint 1

Start at the top-right corner. Moving left finds more 1s; moving down checks whether a later row can beat the best.

FAQ

What is the best time complexity for Row with max 1s?

Optimal (staircase from the top-right) runs in O(n + m) time and O(1) extra space. c moves left at most m times; r moves down n times.

Which pattern does Row with max 1s use?

It is a binary search problem that uses the 2d binary search + step search pattern. Other problems with the same pattern: Search a 2D Matrix, Search a 2D Matrix II (Young Tableau).

Is there a brute force solution for Row with max 1s?

Yes. Binary search each row takes O(n log m) time and O(1) space. In each sorted row, bisectleft(1) gives the first 1, so the row has m - index ones.

Which edge cases should I test for Row with max 1s?

No 1s anywhere; Ties (return the smaller row index).