Problem

Given a m x n binary matrix mat with each row sorted, find the 0-indexed position of the row that contains the maximum count of ones.

You are given a MxN matrix with each row sorted. Matrix is having only 0′s and 1′s. You have to find row wotth maximum number of 1′s.

1
2
3
4
5

000111
001111
011111
000011
111111

Method 1 - Naive

The naive approach involves iterating through each row of the matrix mat and counting the number of 1s in each row. We can then compare the count of 1s for each row to find the row with the maximum number of 1s.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int rowWithMaxOnes(int[][] mat) {
        int maxOnes = 0;
        int ansRow = -1;

        for (int i = 0; i < mat.length; i++) {
            int countOnes = 0;
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 1) {
                    countOnes++;
                }
            }
            if (countOnes > maxOnes) {
                maxOnes = countOnes;
                ansRow = i;
            }
        }

        return ansRow;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def row_with_max_ones(self, mat: List[List[int]]) -> int:
        max_ones = 0
        ans_row = -1
        
        for i, row in enumerate(mat):
            count_ones = row.count(1)
            if count_ones > max_ones:
                max_ones = count_ones
                ans_row = i
        
        return ans_row

Complexity

  • ⏰ Time complexity: O(m * n), where m is the number of rows and n is the number of columns. This is because, in the worst case, we need to check every element in the matrix.
  • 🧺 Space complexity: O(1). The space complexity is constant because no additional space proportional to the input size is used.

Method 2 - Using binary search

To find the row with the maximum number of 1s in a given MxN matrix where each row is sorted (containing only 0s and 1s), we can take advantage of the sorted nature of the rows. Since each row is sorted, all the 1s will appear consecutively after the 0s in the row.

One efficient approach is to utilise a binary search to find the first occurrence of 1 in each row, and then count the number of 1s by calculating the distance from this position to the end of the row. By identifying this in each row, we can determine the row with the maximum number of 1s.

Total number of 1s will be n – index of first 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int rowWithMaxOnes(int[][] matrix) {
        int maxOnes = 0;
        int ansRow = -1;

        for (int i = 0; i < matrix.length; i++) {
            int firstOneIndex = firstOneIndex(matrix[i]);
            int numOnes = matrix[i].length - firstOneIndex;
            if (numOnes > maxOnes) {
                maxOnes = numOnes;
                ansRow = i;
            }
        }

        return ansRow;
    }

    private int firstOneIndex(int[] row) {
        int low = 0;
        int high = row.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (row[mid] == 1) {
                if (mid == 0 || row[mid - 1] == 0) {
                    return mid;
                }
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return row.length; // return the length if no 1 is found
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def row_with_max_ones(self, matrix: List[List[int]]) -> int:
        def first_one_index(row: List[int]) -> int:
            low, high = 0, len(row) - 1
            while low <= high:
                mid = (low + high) // 2
                if row[mid] == 1:
                    if mid == 0 or row[mid - 1] == 0:
                        return mid
                    high = mid - 1
                else:
                    low = mid + 1
            return len(row)  # return the length if no 1 is found
        
        max_ones = 0
        ans_row = -1
        
        for i, row in enumerate(matrix):
            index = first_one_index(row)
            num_ones = len(row) - index
            if num_ones > max_ones:
                max_ones = num_ones
                ans_row = i
        
        return ans_row

Complexity

  • ⏰ Time complexity: O(m log n), because we perform a binary search on each row to find the first occurrence of 1.
  • 🧺 Space complexity: O(1)