Find the Row with Maximum Number of 1s
Binary Search on 2D Arrays DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Find the row with the maximum number of ones in a sorted binary matrix, Arrays, Matrices, Two-dimensional Array Traversal, Brute Force, Binary Search, Time Complexity, Space Complexity, Big O Notation, Loops, Conditional Statements, Optimization, space complexity, matrix traversal, array algorithms, binary search, time complexity analysis, Counting in Sorted Arrays.
Row with Maximum Ones You are given a non empty binary matrix mat of size N rows and M columns. The matrix consists of only 0s and 1s, and all the rows are sorted in ascending order. Your task is to find the 0 indexed row number that contains the maximum number of ones. Note: If multiple rows have the same maximum number of ones, return the smallest 0 indexed row number among them. If the matrix does not contain any '1', return 1. Input Specification: The first line of input contains two integers, N and M, representing the number of rows and columns, respectively. Each of the next N lines contains M integers (0 or 1) separated by spaces, representing the elements of the matrix mat. Output Specification: Print a single integer, the 0 indexed row number with the maximum number of ones, or 1 if no '1' is found in the matrix. Constraints: 1 <= N, M <= 1000 (Inferred from typical competitive programming problem sizes, actual constraints were not provided) mat[i][j] is either 0 or 1. Each row i of mat is sorted in non decreasing order. Sample Test Cases: Example 1: Input: Output: Explanation: Row 0: 3 ones Row 1: 1 one Row 2: 0 ones Row 0 has the maximum number of ones. Example 2: Input: Output: Explanation: The matrix does not contain any '1'. Therefore, 1 is the answer.