⬅ Previous Topic
Print Matrix in Spiral MannerNext Topic ⮕
Search in a Sorted 2D Matrix⬅ Previous Topic
Print Matrix in Spiral MannerNext Topic ⮕
Search in a Sorted 2D MatrixTopic Contents
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.
-1
.maxOnesRow = -1
and maxOnes = 0
.= m - index_of_first_1
is more than maxOnes
, update both maxOnes
and maxOnesRow
.maxOnesRow
.public class MaxOnesRowFinder {
public static int rowWithMaxOnes(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
int maxOnesRow = -1;
int maxOnes = 0;
for (int i = 0; i < n; i++) {
int firstOneIndex = findFirstOne(matrix[i], m);
if (firstOneIndex != -1) {
int onesCount = m - firstOneIndex;
if (onesCount > maxOnes) {
maxOnes = onesCount;
maxOnesRow = i;
}
}
}
return maxOnes == 0 ? -1 : maxOnesRow;
}
private static 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; // Look for earlier 1
} else {
low = mid + 1;
}
}
return index;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 0, 1, 1},
{0, 1, 1, 1},
{0, 0, 0, 1}
};
System.out.println("Row with max 1's: " + rowWithMaxOnes(matrix));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | If all 1s are at the beginning of each row, the binary search terminates quickly for each. |
Average Case | O(n log m) | Binary search is applied to each of the n rows, with log m steps per row. |
Worst Case | O(n log m) | Each row takes log m time to search in worst-case when 1s are at the end. |
O(1)
Explanation: No extra space used other than a few variables.
⬅ Previous Topic
Print Matrix in Spiral MannerNext Topic ⮕
Search in a Sorted 2D MatrixYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.