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.
public class MaxOnesRow {
public static int findRowWithMaxOnes(int[][] matrix) {
int maxRowIndex = -1;
int maxCount = 0;
for (int i = 0; i < matrix.length; i++) {
int count = 0;
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 1) {
count++;
}
}
if (count > maxCount) {
maxCount = count;
maxRowIndex = i;
}
}
return maxRowIndex;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0},
{1, 1, 0, 0}
};
int result = findRowWithMaxOnes(matrix);
System.out.println("Row with maximum number of 1's: " + result);
}
}
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.
public class MaxOnesRow {
public static int binarySearch(int[] row) {
int low = 0, 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; // First occurrence of 1
}
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // No 1 found
}
public static int findRowWithMaxOnes(int[][] matrix) {
int maxRowIndex = -1;
int maxCount = 0;
for (int i = 0; i < matrix.length; i++) {
int index = binarySearch(matrix[i]);
if (index != -1) {
int count = matrix[i].length - index; // Count of 1's
if (count > maxCount) {
maxCount = count;
maxRowIndex = i;
}
}
}
return maxRowIndex;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0},
{1, 1, 0, 0}
};
int result = findRowWithMaxOnes(matrix);
System.out.println("Row with maximum number of 1's: " + result);
}
}
Output:
Row with maximum number of 1's: 1
Method 3: Using Two-Pointer Technique
This method uses an efficient two-pointer approach to find the row with maximum 1's in O(m+n) time complexity.
public class MaxOnesRow {
public static int findRowWithMaxOnes(int[][] matrix) {
int maxRowIndex = 0;
int maxCount = 0;
int j = matrix[0].length - 1; // Start from the last column
// Traverse each row from top to bottom
for (int i = 0; i < matrix.length; i++) {
// Move left until we find 0 or reach start of row
while (j >= 0 && matrix[i][j] == 1) {
j--;
}
// Calculate number of 1's in current row
int currentCount = matrix[i].length - 1 - j;
// Update max if current row has more 1's
if (currentCount > maxCount) {
maxCount = currentCount;
maxRowIndex = i;
}
}
return maxRowIndex;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 0, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0},
{1, 1, 0, 0}
};
int result = findRowWithMaxOnes(matrix);
System.out.println("Row with maximum number of 1's: " + result);
}
}
Output:
Row with maximum number of 1's: 1
Explanation:
This optimized approach works by:
- Starting from the top-right corner of the matrix
- Moving left when encountering a 1 (to find the first 0 in the row)
- Moving down when encountering a 0 (to check the next row)
- Keeping track of the row with the maximum number of 1's found