











Find Row with Maximum no. of 1’s in Python
Row with Maximum no. of 1’s in Python
Here on this page, we will learn how to Find a Row with Maximum no. of 1’s in Python Language.
Example :
- Input : matrix = [ [ 0, 1, 0, 0 ],
[ 1, 0, 0, 1 ],
[ 1, 1, 1, 1 ],
[ 0, 0, 1, 1 ] ] - Output : 3rd Row


Method Discussed :
- Method 1 : Naïve Method
- Method 2 : Using Binary Search.
Algorithm ( Method 1 )
- In this method we will traverse each row of the matrix,
- Find the count of 1’s in each row.
- Then compare it with max_count and the index value.
- After complete iteration, print the value of the index.
Time and Space Complexity :
- Time-Complexity : O(r*c)
- Space-Complexity : O(1)


Python Code
Run
Matrix = [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]] max_count, row = 0, -1 for i in range(4): count = 0 for j in range(4): if Matrix[i][j] == 1: count += 1 if count > max_count: max_count = count row = i print("Row with maximum 1's is :", row+1)
Output
Row with maximum 1's is : 3
Algorithm ( Method 2 )
- Take a variable to hold the index value of required row, let it be index=-1, and max_count=0, that hold the maximum count of 1.
- Now, iterate over each row, and take variable say count=0, to count the number of 1’s in current row.
- For, i-th row, use binary search to find the first instance of 1.
- Then count = No. of columns – first instance of 1.
- Check if count > max_count, then set max_count = count and index=i.
- After the iteration of all rows, print the value of the index.
Time and Space Complexity :
- Time-Complexity : O(r*log(c))
- Space-Complexity : O(1)
Run
def first(arr, low, high): if high >= low: mid = low + (high - low) // 2 if (mid == 0 or arr[mid - 1] == 0) and arr[mid] == 1: return mid elif arr[mid] == 0: return first(arr, (mid + 1), high) else: return first(arr, low, (mid - 1)) return -1 Matrix = [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]] max_count, row = 0, -1 for i in range(4): count = 0 x = first(Matrix[i], 0, 3) if x != -1: count = 4 - x if count > max_count: max_count = count row = i print("Row with maximum 1's is :", row + 1)
Output
Row with maximum 1's is : 3
For similar questions click on the given button
Login/Signup to comment