Row with max 1s

 

PROBLEM 53: Row with max 1s

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 11/04/2023

Given a boolean 2D array of n x m dimensions where each row is sorted. Find the 0-based index of the first row that has the maximum number of 1's.

Example 1:

Input: 
N = 4 , M = 4
Arr[][] = {{0, 1, 1, 1},
           {0, 0, 1, 1},
           {1, 1, 1, 1},
           {0, 0, 0, 0}}
Output: 2
Explanation: Row 2 contains 4 1's (0-based
indexing).

Example 2:

Input: 
N = 2, M = 2
Arr[][] = {{0, 0}, {1, 1}}
Output: 1
Explanation: Row 1 contains 2 1's (0-based
indexing).

Solution :

class Solution:

    def rowWithMax1s(self,arr, n, m):
        # code here
        cnt = 0
        ii = 0
        m = 0
        for i in arr:
            ii = ii + 1
            if i.count(1) > cnt:
                cnt = i.count(1)
                m = ii
        return m-1

if __name__ == '__main__':
    tc = int(input())
    while tc > 0:
        n, m = list(map(int, input().strip().split()))
        
        inputLine = list(map(int, input().strip().split()))
        arr = [[0 for j in range(m)] for i in range(n)]
        
        for i in range(n):
            for j in range(m):
                arr[i][j] = inputLine[i * m + j]
        ob = Solution()
        ans = ob.rowWithMax1s(arr, n, m)
        print(ans)
        tc -= 1

Expected Time Complexity: O(Nlog(M))

Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N, M ≤ 103
0 ≤ Arr[i][j] ≤ 1