Find Row with Maximum Number of 1's
Understanding the Problem
The goal is to find the row in a binary matrix that contains the maximum number of 1's.
Method 1: Simple Iteration
This method iterates through each row and counts the number of 1's.
#include <iostream>
using namespace std;
int findRowWithMaxOnes(int matrix[][100], int rows, int cols) {
int maxRowIndex = -1;
int maxCount = 0;
for (int i = 0; i < rows; i++) {
int count = 0;
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
count++;
}
}
if (count > maxCount) {
maxCount = count;
maxRowIndex = i;
}
}
return maxRowIndex;
}
int main() {
int matrix[100][100] = {
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0},
{1, 1, 0, 0}
};
int rows = 4, cols = 4;
int result = findRowWithMaxOnes(matrix, rows, cols);
cout << "Row with maximum number of 1's: " << result << endl;
return 0;
}
Output:
Row with maximum number of 1's: 1
Method 2: Using Binary Search
This method assumes each row is sorted and uses binary search to find the first 1.
#include <iostream>
using namespace std;
int binarySearch(int row[], int cols) {
int low = 0, high = cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (row[mid] == 1) {
if (mid == 0 || row[mid - 1] == 0) {
return mid; // First occurrence of 1
}
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // No 1 found
}
int findRowWithMaxOnes(int matrix[][100], int rows, int cols) {
int maxRowIndex = -1;
int maxCount = 0;
for (int i = 0; i < rows; i++) {
int index = binarySearch(matrix[i], cols);
if (index != -1) {
int count = cols - index; // Count of 1's
if (count > maxCount) {
maxCount = count;
maxRowIndex = i;
}
}
}
return maxRowIndex;
}
int main() {
int matrix[100][100] = {
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0},
{1, 1, 0, 0}
};
int rows = 4, cols = 4;
int result = findRowWithMaxOnes(matrix, rows, cols);
cout << "Row with maximum number of 1's: " << result << endl;
return 0;
}
Output:
Row with maximum number of 1's: 1
Method 3: Using Two-Pointer Technique
This method uses a two-pointer technique to efficiently find the row with the maximum number of 1's in O(m+n) time complexity.
#include <iostream>
using namespace std;
int findRowWithMaxOnes(int matrix[][100], int rows, int cols) {
int maxRowIndex = 0;
int maxCount = 0;
int j = cols - 1; // Start from the last column
for (int i = 0; i < rows; i++) {
// Move left until we find a 0 or reach the start of the row
while (j >= 0 && matrix[i][j] == 1) {
j--; // Move left
}
int count = cols - 1 - j; // Count of 1's in the current row
if (count > maxCount) {
maxCount = count;
maxRowIndex = i;
}
}
return maxRowIndex;
}
int main() {
int matrix[100][100] = {
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0},
{1, 1, 0, 0}
};
int rows = 4, cols = 4;
int result = findRowWithMaxOnes(matrix, rows, cols);
cout << "Row with maximum number of 1's: " << result << endl;
return 0;
}
Output:
Row with maximum number of 1's: 1
Explanation:
This method is the most efficient with O(m+n) time complexity when:
- The matrix is row-wise sorted (each row is sorted in non-decreasing order)
- We start from the top-right corner of the matrix
- We move left when we find a 1 and down when we find a 0
- We keep track of the row with the maximum number of 1's encountered