Row with max 1s

Time: O(n+m)

Space: O(1)

Intuition

Find row with maximum 1s in a binary matrix where each row is sorted. Start from top-right corner, move left (1s) or down (0s).

Algorithm

1Start at (0, n-1). If cell is 1: move left (col--), update max row. If 0: move down (row++).

Common Pitfalls

•O(m+n) algorithm. Since rows are sorted, once you find a 1, all elements to the left are also 1.

Row with max 1s.java

Java

// Approach: Start from top-right corner: move left on 1, move down on 0. Track row with most 1s.
// Time: O(n+m) Space: O(1)
class Solution {
    public int rowWithMax1s(int arr[][]) {
        int res = -1;
        int n = arr.length;
        int m = arr[0].length;
        int j = m - 1;
        int i = 0;

        while (i < n && j >= 0) {
            if (arr[i][j] == 1) {
                j--;
                res = i;
            } else
                i++;
        }

        return res;
    }
}

Was this solution helpful?