Find the Row with Maximum 1s in a Sorted Binary Matrix

75.2k
0

Given a non-empty grid mat consisting of only 0s and 1s, where all the rows are sorted in ascending order, find the index of the row with the maximum number of ones.

If two rows have the same number of ones, consider the one with a smaller index. If no 1 exists in the matrix, return -1.

Example 1

Input: mat = [[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1]]

Output: 1

Explanation: Row 1 has 3 ones, which is more than any other row.

Example 2

Input: mat = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Output: -1

Explanation: No row contains even a single 1, so the answer is -1.

Brute Force Approach

The most direct idea is simple: count how many 1s are present in every row, then keep the row with the largest count.

This approach does not try to use the sorted property at all.

Algorithm

  • Start with maxCount = 0 and answer = -1. This is done so the answer can stay -1 if the full matrix contains no 1.

  • Traverse the matrix row by row because each row needs its own count.

  • For the current row, scan every column and count how many cells contain 1.

  • After finishing that row, compare its count with maxCount.

  • If the current row has more 1s, update maxCount and store its row index in answer because a better row has been found.

  • After all rows are processed, return answer because it stores the row with the highest number of 1s, or -1 if none were found.

Dry Run

Find Row with Maximum Number of 1's Brute Dry Run

Find Row with Maximum Number of 1's Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the index of the row
with the maximum number of 1s.
*/
int rowWithMax1s(vector<vector<int>>& mat) {
// Store the best count of 1s found so far.
int maxCount = 0;
// Store the row index that gives the current best answer.
int answer = -1;
for (int i = 0; i < (int)mat.size(); i++) {
// Count the number of 1s in the current row.
int count = 0;
for (int j = 0; j < (int)mat[i].size(); j++) {
if (mat[i][j] == 1) {
count++;
}
}
// Update the answer because this row has more 1s.
if (count > maxCount) {
maxCount = count;
answer = i;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<vector<int>> mat = {
{0, 0, 1, 1},
{0, 1, 1, 1},
{0, 0, 0, 1}
};
Solution obj;
cout << obj.rowWithMax1s(mat) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M x N),M is the number of rows and N is the length of each row, because every cell of the matrix may need to be checked.

Space Complexity: O(1), because constant space is used.

Better Approach

In a sorted binary row, all 0s come first and all 1s come after them. So instead of counting every cell, it is enough to find the first 1. Once its position is known, the number of 1s in that row is easy to calculate.

If the row has N columns and the first 1 appears at index k, then the row has N - k ones.

So the real problem becomes: for each row, find where the 1s begin.

Algorithm

  • Start with answer = -1 and maxCount = 0 so the answer can remain -1 when the matrix has no 1.

  • For each row, use binary search to find the first position where 1 appears.

  • Binary search is used because the row is sorted, so once a 1 is found, the search can move left to check whether an earlier 1 exists.

  • If no 1 is found in the row, skip that row because it cannot improve the answer.

  • If the first 1 is found at index firstOne, compute the number of 1s as columns - firstOne.

  • Compare that count with maxCount, and update answer when the current row has more 1s.

  • After all rows are processed, return answer.

Dry Run

Better

Better

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the index of the row
with the maximum number of 1s.
*/
int rowWithMax1s(vector<vector<int>>& mat) {
// Store the best count of 1s found so far.
int maxCount = 0;
// Store the row index that gives the current best answer.
int answer = -1;
int rows = (int)mat.size();
int cols = (int)mat[0].size();
for (int i = 0; i < rows; i++) {
// Search for the first 1 in the current row.
int low = 0;
int high = cols - 1;
int firstOne = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
// A 1 is found, so store it and keep searching left.
if (mat[i][mid] == 1) {
firstOne = mid;
high = mid - 1;
} else {
// A 0 means the first 1 can only be on the right side.
low = mid + 1;
}
}
// Skip rows that do not contain any 1.
if (firstOne == -1) {
continue;
}
// Count 1s using the first position where they begin.
int count = cols - firstOne;
// Update the answer because this row has more 1s.
if (count > maxCount) {
maxCount = count;
answer = i;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<vector<int>> mat = {
{0, 0, 1, 1},
{0, 1, 1, 1},
{0, 0, 0, 1}
};
Solution obj;
cout << obj.rowWithMax1s(mat) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M x log N), M is the number of rows and N is the length of each row, because binary search is performed for every row.

Space Complexity: O(1), because constant space is used.

Optimal Approach

We want to find the row with the maximum number of 1s in a row-wise sorted binary matrix. Because every row is sorted, all 0s appear first followed by all 1s. This means the row with the most 1s is simply the row where the first 1 appears furthest to the left.

Instead of counting 1s in every row from scratch, we track the leftmost column containing a 1 seen so far, starting from the top-right corner (0, cols - 1).

  • When the current cell is 1:

    The current row is now our best candidate because it contains a 1 at or to the left of our current column. We move left (col--) to check if this same row has even more 1s further to the left.

  • When the current cell is 0:

    Since the row is sorted, every cell to the left of a 0 in this row must also be 0. This means the current row cannot beat our best candidate. We move down (row++) to test the next row against our target column.

  • After moving down to a new row (whether after a 0 or reaching a 1 boundary):

    We resume checking from the exact same column where we stopped in the previous row.

    • If the cell in the new row is 0, it means this new row has fewer or equal 1s compared to our current best row. It cannot beat our best candidate, so we immediately move down again (row++) to skip it.

    • If the cell in the new row is 1, it means this row matches or beats our record. We then move left (col--) to see how many more 1s it contains.

Every move either eliminates one full row (by moving down) or moves our record mark further left (by moving left). Since there are R rows and C columns, we make at most R + C moves, giving a total time complexity of O(R + C).

Algorithm

  • Start from the top-right cell using row = 0 and col = columns - 1 because this position helps decide quickly whether to move left or down.

  • Keep answer = -1 at the beginning so the result stays -1 if no 1 is ever found.

  • While the current position is inside the matrix, check the value at mat[row][col].

  • If the value is 1, store the current row in answer and move left because finding a 1 here means this row may contain even more 1s further left.

  • If the value is 0, move down because this row cannot improve the current column position anymore.

  • Continue until the pointer moves outside the matrix.

  • Return answer because the row that pushed the pointer furthest left must be the row with the maximum number of 1s.

Dry Run

Optimal

Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the index of the row
with the maximum number of 1s.
*/
int rowWithMax1s(vector<vector<int>>& mat) {
int rows = (int)mat.size();
int cols = (int)mat[0].size();
// Start from the top-right corner of the matrix.
int row = 0;
// This column pointer moves left whenever a better row is found.
int col = cols - 1;
// Store the row index that currently has the maximum number of 1s.
int answer = -1;
// Keep moving while the current cell stays inside the matrix.
while (row < rows && col >= 0) {
// A 1 means this row reaches at least this far left.
if (mat[row][col] == 1) {
answer = row;
col--;
} else {
// A 0 means this row cannot improve the current column position.
row++;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<vector<int>> mat = {
{0, 0, 1, 1},
{0, 1, 1, 1},
{0, 0, 0, 1}
};
Solution obj;
cout << obj.rowWithMax1s(mat) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M + N), M is the number of rows and N is the length of each row, because each move goes either one row down or one column left.

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

Because each row has all 0s first and all 1s later. That lets the solution find where 1s begin instead of counting every cell one by one.

Two PointerBinary SearchSortingMathsArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0