Find the Row with Maximum 1's in a Binary Matrix Optimal Approach using Binary Search

Matrix - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a binary matrix of size n x m, where each row is sorted (0s appear before 1s), your task is to find the index of the row that contains the maximum number of 1's.

  • If multiple rows have the same number of 1's, return the index of the first such row.
  • If the matrix is empty or contains no 1's at all, return -1.

Examples❯

Matrix Output Description
[[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1]]
1 Row 1 has 3 ones, more than any other row.
[[0, 0, 0], [0, 0, 1], [0, 1, 1]]
2 Row 2 has 2 ones, the highest among all.
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
-1 No row contains a 1.
[[1, 1, 1], [1, 1, 1], [1, 1, 1]]
0 All rows have 3 ones, return the first row index.
[] -1 Matrix is empty, so no rows to check.
[[0, 1, 1], [0, 1, 1], [0, 1, 1]]
0 All rows have 2 ones, return index of the first.
[[0, 0, 1], [1, 1, 1], [0, 1, 1]]
1 Row 1 has 3 ones, which is the maximum.
[[0, 0], [0, 0], [1, 1]]
2 Only row 2 has ones.

Solution❯

Understanding the Problem

We are given a binary matrix where each row is sorted in non-decreasing order — that means all 0s come before any 1s in every row. Our task is to find the index of the row that contains the maximum number of 1's.

If multiple rows have the same highest number of 1’s, we must return the first such row (the one with the smallest index). If the matrix is empty or has no 1’s at all, we return -1.

Since rows are sorted, this opens the door for a faster approach than simply scanning each cell — we can use binary search to find the first 1 in each row and calculate the count of 1s from there.

Step-by-Step Solution with Example

Step 1: Take a sample input

matrix = [
  [0, 0, 1, 1],
  [0, 1, 1, 1],
  [0, 0, 0, 1]
]

This matrix has 3 rows. Each row is sorted.

Step 2: Use binary search on each row

For each row, we perform binary search to find the first occurrence of 1. Since the row is sorted, once we know where 1s begin, we can count the number of 1s as number_of_1s = total_columns - index_of_first_1.

Step 3: Go row by row

  • Row 0: Binary search gives first 1 at index 2 → 2 ones
  • Row 1: First 1 at index 1 → 3 ones
  • Row 2: First 1 at index 3 → 1 one

Row 1 has the most 1s. So, the answer is 1.

Step 4: Keep track of max count and row index

As we process each row, we store the max count of 1s found so far and update the result row index if we find a row with more 1s.

Edge Cases

  • Matrix is empty: Return -1
  • All elements are 0: No 1s found → Return -1
  • All rows have same number of 1s: Return index of the first such row
  • First row is full of 1s: We can stop early because no other row can have more 1s

Finally

This problem becomes much simpler once we realize that rows are sorted. Using binary search for each row significantly speeds up our solution compared to brute-force scanning. This solution works efficiently even for large matrices with a time complexity of O(n log m), where n is the number of rows and m is the number of columns.

For beginners, always look for problem constraints (like sorted rows) that you can exploit using optimized techniques like binary search.

Algorithm Steps❯

  1. Initialize maxOnesRow = -1 and maxOnes = 0.
  2. For each row, do binary search to find the index of first 1.
  3. If number of 1s in the row = m - index_of_first_1 is more than maxOnes, update both maxOnes and maxOnesRow.
  4. After checking all rows, return maxOnesRow.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findFirstOne(int row[], int m) {
    int low = 0, high = m - 1, index = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (row[mid] == 1) {
            index = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return index;
}

int rowWithMaxOnes(int matrix[][4], int n, int m) {
    int maxRow = -1, maxOnes = 0;
    for (int i = 0; i < n; i++) {
        int first = findFirstOne(matrix[i], m);
        if (first != -1 && m - first > maxOnes) {
            maxOnes = m - first;
            maxRow = i;
        }
    }
    return maxRow;
}

int main() {
    int matrix[3][4] = {{0, 0, 1, 1}, {0, 1, 1, 1}, {0, 0, 0, 1}};
    printf("Row with max 1's: %d\n", rowWithMaxOnes(matrix, 3, 4));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)If all 1s are at the beginning of each row, the binary search terminates quickly for each.
Average CaseO(n log m)Binary search is applied to each of the n rows, with log m steps per row.
Worst CaseO(n log m)Each row takes log m time to search in worst-case when 1s are at the end.

Space Complexity❯

O(1)

Explanation: No extra space used other than a few variables.

Problem Statement❯

Given a binary matrix of size n x m, where each row is sorted (0s appear before 1s), your task is to find the index of the row that contains the maximum number of 1's.

  • If multiple rows have the same number of 1's, return the index of the first such row.
  • If the matrix is empty or contains no 1's at all, return -1.

Examples❯

Matrix Output Description
[[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1]]
1 Row 1 has 3 ones, more than any other row.
[[0, 0, 0], [0, 0, 1], [0, 1, 1]]
2 Row 2 has 2 ones, the highest among all.
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
-1 No row contains a 1.
[[1, 1, 1], [1, 1, 1], [1, 1, 1]]
0 All rows have 3 ones, return the first row index.
[] -1 Matrix is empty, so no rows to check.
[[0, 1, 1], [0, 1, 1], [0, 1, 1]]
0 All rows have 2 ones, return index of the first.
[[0, 0, 1], [1, 1, 1], [0, 1, 1]]
1 Row 1 has 3 ones, which is the maximum.
[[0, 0], [0, 0], [1, 1]]
2 Only row 2 has ones.

Solution❯

Understanding the Problem

We are given a binary matrix where each row is sorted in non-decreasing order — that means all 0s come before any 1s in every row. Our task is to find the index of the row that contains the maximum number of 1's.

If multiple rows have the same highest number of 1’s, we must return the first such row (the one with the smallest index). If the matrix is empty or has no 1’s at all, we return -1.

Since rows are sorted, this opens the door for a faster approach than simply scanning each cell — we can use binary search to find the first 1 in each row and calculate the count of 1s from there.

Step-by-Step Solution with Example

Step 1: Take a sample input

matrix = [
  [0, 0, 1, 1],
  [0, 1, 1, 1],
  [0, 0, 0, 1]
]

This matrix has 3 rows. Each row is sorted.

Step 2: Use binary search on each row

For each row, we perform binary search to find the first occurrence of 1. Since the row is sorted, once we know where 1s begin, we can count the number of 1s as number_of_1s = total_columns - index_of_first_1.

Step 3: Go row by row

  • Row 0: Binary search gives first 1 at index 2 → 2 ones
  • Row 1: First 1 at index 1 → 3 ones
  • Row 2: First 1 at index 3 → 1 one

Row 1 has the most 1s. So, the answer is 1.

Step 4: Keep track of max count and row index

As we process each row, we store the max count of 1s found so far and update the result row index if we find a row with more 1s.

Edge Cases

  • Matrix is empty: Return -1
  • All elements are 0: No 1s found → Return -1
  • All rows have same number of 1s: Return index of the first such row
  • First row is full of 1s: We can stop early because no other row can have more 1s

Finally

This problem becomes much simpler once we realize that rows are sorted. Using binary search for each row significantly speeds up our solution compared to brute-force scanning. This solution works efficiently even for large matrices with a time complexity of O(n log m), where n is the number of rows and m is the number of columns.

For beginners, always look for problem constraints (like sorted rows) that you can exploit using optimized techniques like binary search.

Algorithm Steps❯

  1. Initialize maxOnesRow = -1 and maxOnes = 0.
  2. For each row, do binary search to find the index of first 1.
  3. If number of 1s in the row = m - index_of_first_1 is more than maxOnes, update both maxOnes and maxOnesRow.
  4. After checking all rows, return maxOnesRow.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findFirstOne(int row[], int m) {
    int low = 0, high = m - 1, index = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (row[mid] == 1) {
            index = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return index;
}

int rowWithMaxOnes(int matrix[][4], int n, int m) {
    int maxRow = -1, maxOnes = 0;
    for (int i = 0; i < n; i++) {
        int first = findFirstOne(matrix[i], m);
        if (first != -1 && m - first > maxOnes) {
            maxOnes = m - first;
            maxRow = i;
        }
    }
    return maxRow;
}

int main() {
    int matrix[3][4] = {{0, 0, 1, 1}, {0, 1, 1, 1}, {0, 0, 0, 1}};
    printf("Row with max 1's: %d\n", rowWithMaxOnes(matrix, 3, 4));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)If all 1s are at the beginning of each row, the binary search terminates quickly for each.
Average CaseO(n log m)Binary search is applied to each of the n rows, with log m steps per row.
Worst CaseO(n log m)Each row takes log m time to search in worst-case when 1s are at the end.

Space Complexity❯

O(1)

Explanation: No extra space used other than a few variables.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...