Answer» - Brute force method: An easy WAY is to traverse the matrix row by row, counting the amount of 1s in each row, and comparing the count to the maximum. Finally, with a maximum of 1s, return the index of the row. This approach has an O(m*n) time complexity, where m is the number of rows and n is the number of columns in the matrix.
- Optimized approach using binary SEARCH: We can still do better. We can use Binary Search to count the number of 1s in each row because each row is sorted. In each row, we obtain the index of the first occurrence of 1. The entire number of columns MINUS the index of the first 1 will equal the number of 1s. The time complexity for this approach will be O(mlogn).
- Further Optimization: The previous solution can be improved somewhat more. Instead of performing a binary search in each row, we first determine whether the row has more 1s than the maximum number of 1s. If there are additional 1s in the row, only count the 1s. We also don't execute a binary search across the entire row to count 1s in a row; instead, we search before the index of the last max. The worst-case time complexity is also O(mLogn), but the will solution performs better on average.
int rowWMax1s(bool matrix[m][n]){ int i, index; // Initialize maximum by using the values of the first row. int max_rowIndex = 0; int maximum = first(matrix[0], 0, C - 1); // count number of 1s while traversing each row // by CHECKING the index of the first 1 for (i = 1; i < m; i++) { // Count 1s for this row only; if this row // has greater number of 1s than maximum so far if (maximum != -1 && matrix[i][n - maximum - 1] == 1) { index = first (matrix[i], 0, n - maximum); if (index != -1 && n - index > maximum) { maximum = n - index; max_rowIndex = i; } } else { maximum = first(matrix[i], 0, n - 1); } } return max_rowIndex;}Here, the variable maximum is first initialized by using the values of the first row. We then check to see if the row has more 1s than the maximum number of 1s. Only count the 1s if there are any more in the row. To count 1s in a row, we don't run a binary search across the full row; instead, we search before the index of the last maximum.
|
