☕ DSA Java Articles

Topics › Binary Search › BS on 2D Arrays

Find row with maximum 1's

Easy TUF ID 66 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an n × m binary matrix in which every row is sorted: within a row all the 0s come first, followed by all the 1s. Return the index of the row that contains the most 1s. If several rows tie, return the smallest such index. If the matrix contains no 1 at all, return -1.

Constraints: 1 ≤ n, m ≤ 1000, every cell is 0 or 1, every row is non-decreasing.

Example 1

mat = [[1, 1, 1],
       [0, 0, 1],
       [0, 0, 0]]
answer = 0           // row 0 has three 1s, more than any other row

Example 2

mat = [[0, 0, 1],
       [0, 1, 1],
       [0, 0, 1]]
answer = 1           // row 1 has two 1s; rows 0 and 2 have one each

Example 3

mat = [[0, 0],
       [0, 0]]
answer = -1          // no 1 anywhere

The sorted rows are the whole point. In an unsorted matrix nothing beats counting every cell, but when each row is 0...01...1, the number of 1s in a row is determined by where the first 1 is, and that position can be found without touching every cell.

Approach 1: Brute force, count every row

Intuition. Count the 1s in each row and remember the row with the largest count. Update the best row only on a strictly larger count, so that an earlier row keeps the title over a later row with the same count. Starting the best count at 0 and the best row at -1 makes a matrix without 1s return -1 automatically.

Algorithm.

  1. Set bestRow = -1, bestCount = 0.
  2. For each row, count its 1s; if the count exceeds bestCount, record this row.
  3. Return bestRow.
static int bruteForce(int[][] mat) {
    int n = mat.length;
    int bestRow = -1, bestCount = 0;
    for (int r = 0; r < n; r++) {
        int count = 0;
        for (int x : mat[r]) if (x == 1) count++;
        if (count > bestCount) { bestCount = count; bestRow = r; }
    }
    return bestRow;
}

Complexity. Time O(n × m): every cell is visited once. Space O(1).

This ignores the sorted order entirely. For n = m = 1000 it is a million steps, fine in practice, but the structure of the input allows much less.

Approach 2: Better, binary search each row

Intuition. In a row of the form 0...01...1, the count of 1s equals m minus the index of the first 1. Finding the first 1 is the classic lower bound search: look at the middle cell; if it is 1, the first 1 is here or to the left, so remember this index and search the left half; if it is 0, the first 1 must be to the right. If the row has no 1, the search returns m and the count is 0.

Algorithm.

  1. For each row, binary search the index of its first 1 (or m if none).
  2. The row’s count is m − firstOne; keep the row with the strictly largest count.
static int firstOne(int[] row) {
    int lo = 0, hi = row.length - 1, ans = row.length;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (row[mid] == 1) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

static int better(int[][] mat) {
    int n = mat.length;
    int bestRow = -1, bestCount = 0;
    for (int r = 0; r < n; r++) {
        int count = mat[r].length - firstOne(mat[r]);
        if (count > bestCount) { bestCount = count; bestRow = r; }
    }
    return bestRow;
}

Complexity. Time O(n log m): one binary search per row. Space O(1).

This is the approach most people reach for, and it is a good one. But each row’s search starts from scratch, even though knowing that some row has, say, 7 ones already tells us that any row with 7 or fewer ones can be dismissed the moment we see a 0 at column m − 7.

Approach 3: Optimal, the staircase walk

Intuition. Start in the top-right corner. Keep a column pointer c such that the current best row has 1s in every column from c + 1 to m − 1. Now examine mat[r][c] for the current row r:

Each step moves either left or down, so the walk takes at most n + m − 1 steps. The best row is only replaced on a strict improvement, which gives the smallest index among tied rows for free.

Algorithm.

  1. Start at r = 0, c = m − 1, bestRow = -1.
  2. While r < n and c >= 0: if mat[r][c] == 1, set bestRow = r and c--; else r++.
  3. Return bestRow.
static int optimal(int[][] mat) {
    int n = mat.length;
    if (n == 0) return -1;
    int m = mat[0].length;
    int r = 0, c = m - 1, bestRow = -1;
    while (r < n && c >= 0) {
        if (mat[r][c] == 1) { bestRow = r; c--; }   // row r has at least m - c ones: a new strict maximum
        else r++;                                   // row r has at most m - c - 1 ones: it cannot beat bestRow
    }
    return bestRow;
}

Dry run on Example 2, mat = [[0,0,1],[0,1,1],[0,0,1]]:

r c mat[r][c] action bestRow
0 2 1 row 0 has ≥ 1 one; move left 0
0 1 0 row 0 cannot improve; move down 0
1 1 1 row 1 has ≥ 2 ones; move left 1
1 0 0 move down 1
2 0 0 move down 1

r reaches 3, the loop ends, and the answer is 1.

Complexity. Time O(n + m): each iteration decrements c or increments r, and together they can only move n + m times. Space O(1).

The staircase walk is strictly better than O(n log m) when m is large relative to log m, and it is also the easiest version to get right once the invariant (“columns c + 1 .. m − 1 of bestRow are all 1”) is clear.

Edge cases and pitfalls