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).
Your Task:  
You don't need to read input or print anything. Your task is to complete the function rowWithMax1s() which takes the array of booleans arr[][], n and m as input parameters and returns the 0-based index of the first row that has the most number of 1s. If no such row exists, return -1.
 
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, M ≤ 10^{3}
0 ≤ Arr[i][j] ≤ 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3

class Solution:



	def rowWithMax1s(self,arr, n, m):

		# code here

Solutions:
class Solution:

	def rowWithMax1s(self, arr, n, m):
		max_count = 0
		ans = -1
		for (i, v) in enumerate(arr):
			count = v.count(1)
			if count > max_count:
				max_count = count
				ans = i
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		binary = []
		for x in range(n):
			binary.append(int(''.join(list(map(str, arr[x]))), 2))
		if max(binary) != 0:
			return binary.index(max(binary))
		return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		(i, j) = (0, m - 1)
		index = 0
		while i != n and j != -1:
			if arr[i][j] == 1:
				j -= 1
				index = i
			else:
				i += 1
		if j == m - 1 and i == n:
			return -1
		return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		count = 0
		op = -1
		for i in range(0, n):
			t = sum(arr[i])
			if t > count:
				count = t
				op = i
		return op


class Solution:

	def rowWithMax1s(self, arr, n, m):
		maxi = 0
		ans = -1
		for i in range(n):
			count = 0
			for j in range(m):
				if arr[i][j] == 1:
					count += 1
			if count > maxi:
				maxi = count
				ans = i
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max_row_index = -1
		max_ones_count = 0
		j = m - 1
		for i in range(n):
			while j >= 0 and arr[i][j] == 1:
				j -= 1
			if j < m - 1:
				ones_count = m - 1 - j
				if ones_count > max_ones_count:
					max_ones_count = ones_count
					max_row_index = i
		return max_row_index


import bisect

class Solution:

	def rowWithMax1s(self, arr, n, m):
		rowIndex = -1
		row = 0
		col = m - 1
		while row < n and col >= 0:
			if arr[row][col] == 1:
				rowIndex = row
				col -= 1
			if arr[row][col] == 0:
				row += 1
		return rowIndex


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max = 0
		ans = -1
		for i in range(n):
			cnt = 0
			for j in range(m):
				if arr[i][j] == 1:
					cnt += 1
			if cnt > max:
				ans = i
				max = cnt
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max_val = 0
		max_index = -1
		for x in range(len(arr)):
			total = 0
			for y in range(len(arr[0])):
				total += arr[x][y]
			if total > max_val:
				max_val = total
				max_index = x
		return max_index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max1srow = -1
		(row, col) = (0, m - 1)
		while row < n and col >= 0:
			if arr[row][col]:
				max1srow = row
				while col >= 0 and arr[row][col] == 1:
					col -= 1
			row += 1
		return max1srow


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max1s = 0
		max1srow = -1
		for i in arr:
			ones = m
			for j in i:
				if j == 0:
					ones -= 1
			if ones > max1s:
				max1s = ones
				max1srow = arr.index(i)
		return max1srow


class Solution:

	def rowWithMax1s(self, mat, n, m):
		ans = -1
		min_col = int(1000000000.0)
		for row in range(n):
			(low, high) = (0, m - 1)
			first_occur_one = -1
			while low <= high:
				mid = low + (high - low) // 2
				if mat[row][mid] == 1:
					first_occur_one = mid
					high = mid - 1
				else:
					low = mid + 1
			if first_occur_one != -1:
				if min_col > first_occur_one:
					min_col = first_occur_one
					ans = row
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		mx = 0
		pos = -1
		for i in range(0, len(arr)):
			sm = 0
			for j in range(0, len(arr[i])):
				sm += arr[i][j]
			if sm > mx:
				mx = sm
				pos = i
		return pos


class Solution:

	def rowWithMax1s(self, arr, n, m):
		(val, r_sum, maxSum) = (0, 0, 0)
		for r in range(n):
			for c in range(m):
				r_sum += arr[r][c]
			if r_sum > maxSum:
				maxSum = r_sum
				val = r
			r_sum = 0
		if maxSum == 0:
			return -1
		return val


class Solution:

	def rowWithMax1s(self, arr, n, m):
		m = 0
		for i in arr:
			s = sum(i)
			m = max(s, m)
		if m == 0:
			return -1
		for i in range(n):
			if sum(arr[i]) == m:
				return i


class Solution:

	def rowWithMax1s(self, arr, n, m):
		ans = fin = t = 0
		for i in range(n):
			c = 0
			for j in range(m):
				if arr[i][j] == 1:
					c += 1
					t = 1
			if c > ans:
				ans = c
				fin = i
			if ans == m:
				return i
		if t == 0:
			return -1
		return fin


class Solution:

	def rowWithMax1s(self, arr, n, m):
		ans = -1
		ansm = m
		for i in range(len(arr)):
			for j in range(len(arr[i])):
				if arr[i][j] == 1:
					if j < ansm:
						ans = i
						ansm = j
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max_ele = 0
		max_ind = 0
		for i in range(n):
			if max_ele < sum(arr[i]):
				max_ele = sum(arr[i])
				max_ind = i
		if max_ele == 0:
			return -1
		return max_ind


class Solution:

	def rowWithMax1s(self, arr, n, m):
		(prev, ans) = (0, -1)
		for i in range(n):
			(l, r) = (0, m - 1)
			while l < r:
				mid = l + (r - l) // 2
				if arr[i][mid] == 1:
					r = mid - 1
				else:
					l = mid + 1
			if arr[i][l] == 1:
				if m - l > prev:
					ans = i
					prev = m - l
			elif m - l - 1 > prev:
				ans = i
				prev = m - l - 1
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		one_sum = 0
		for i in range(n):
			curr_one_sum = sum(arr[i])
			if curr_one_sum > one_sum:
				one_sum = curr_one_sum
				indx = i
		if one_sum > 0:
			return indx
		return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		count = 0
		temp = 0
		index = -1
		for i in range(n):
			for j in range(m):
				if arr[i][j] == 1:
					temp += 1
			if temp > count:
				count = temp
				index = i
			temp = 0
		return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		x = [len([i for i in j if i == 1]) for j in arr]
		if max(x) == 0:
			return -1
		return x.index(max(x))


class Solution:

	def rowWithMax1s(self, arr, n, m):
		c = 0
		p = 0
		indx = 0
		for i in range(n):
			c = 0
			for j in range(m):
				if arr[i][j] == 1:
					c += 1
			if c > p:
				p = c
				indx = i
		if p == 0:
			return -1
		return indx


class Solution:

	def rowWithMax1s(self, arr, n, m):
		ans = -1
		row = 0
		column = m - 1
		while row < n and column >= 0:
			if arr[row][column] == 1:
				column -= 1
				ans = row
			else:
				row += 1
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		result = -1
		maximum = 0
		for i in range(len(arr)):
			temp = sum(arr[i])
			if maximum < temp:
				maximum = temp
				result = i
		return result


class Solution:

	def rowWithMax1s(self, arr, n, m):
		ma = -1
		mc = 0
		for i in range(n):
			oc = arr[i].count(1)
			if oc > mc:
				mc = oc
				ma = i
		return ma
		if ma == 0:
			return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		a = 0
		mi = 0
		ri = -1
		kc = 0
		for i in range(0, n):
			rc = 0
			for j in range(0, m):
				if arr[i][j] == 1:
					rc = rc + 1
					if rc > kc:
						kc = rc
						ri = i
		return ri


class Solution:

	def rowWithMax1s(self, arr, n, m):
		count = 0
		ans = -1
		for i in range(n):
			summ = sum(arr[i])
			if summ > count:
				count = summ
				ans = i
		return ans


import bisect

class Solution:

	def rowWithMax1s(self, arr, n, m):
		ans = -1
		count = m
		for i in range(n):
			x = bisect.bisect_left(arr[i], 1)
			if x < count:
				ans = i
				count = x
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		d = {}
		for i in range(len(arr)):
			d[i] = arr[i].count(1)
		max = 0
		ans = 0
		for (a, b) in d.items():
			if int(b) > max:
				max = int(b)
				ans = int(a)
		if max == 0:
			return -1
		else:
			return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		count = 0
		temp1 = -1
		for i in range(0, len(arr)):
			temp = arr[i].count(1)
			if temp > count:
				temp1 = i
				count = temp
		if temp1 == -1:
			return -1
		else:
			return temp1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		maxones = 0
		maxindex = -1
		for i in range(len(arr)):
			rowcount = 0
			for j in range(len(arr[i])):
				if arr[i][j] == 1:
					rowcount += arr[i][j]
			if rowcount > maxones:
				maxones = rowcount
				maxindex = i
		return maxindex


class Solution:

	def rowWithMax1s(self, arr, n, m):
		(i, j) = (0, m - 1)
		count = 0
		index = 0
		ans = 0
		while i <= n - 1 and j >= 0:
			if arr[i][j] == 1:
				j -= 1
				count += 1
				index = i
			else:
				i += 1
				z = i
				for k in range(z, n):
					if arr[k][j] == 0:
						i += 1
					else:
						break
		if count == 0:
			return -1
		else:
			return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max = 0
		row = 0
		for i in range(n):
			count = 0
			for j in range(m):
				if arr[i][j] == 1:
					count += 1
				if count > max:
					max = count
					row = i
		if max == 0:
			return -1
		else:
			return row


class Solution:

	def rowWithMax1s(self, arr, n, m):
		for col in range(m):
			for row in range(n):
				if arr[row][col] == 1:
					return row
		return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		b = []
		for i in range(n):
			b.append(arr[i].count(1))
		if max(b) == 0:
			return -1
		else:
			res = b.index(max(b))
		return res


class Solution:

	def rowWithMax1s(self, arr, n, m):
		i = 0
		j = m - 1
		ans = -1
		while i < n and j >= 0:
			if arr[i][j] == 1:
				ans = i
				j -= 1
			if arr[i][j] == 0:
				i += 1
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		r = 0
		c = m - 1
		max_row_index = -1
		while r < n and c >= 0:
			if arr[r][c] == 1:
				max_row_index = r
				c -= 1
			else:
				r += 1
		return max_row_index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		res = -1
		mx = 0
		for i in range(len(arr)):
			count = 0
			for j in range(len(arr[i])):
				if arr[i][j] == 1:
					count += 1
			if count > mx:
				mx = count
				res = i
		return res


class Solution:

	def rowWithMax1s(self, arr, n, m):
		res = []
		for i in arr:
			res.append(sum(i))
		if max(res) == 0:
			return -1
		return res.index(max(res))


class Solution:

	def rowWithMax1s(self, arr, n, m):
		temp = 0
		ans = 0
		for i in range(len(arr)):
			cnt = arr[i].count(1)
			if cnt > temp:
				temp = cnt
				ans = i
		if temp == 0 and ans == 0:
			return -1
		return ans


class Solution:

	def rowWithMax1s(self, arr, n, m):
		currCol = len(arr[0])
		currRow = -1
		for r in range(len(arr)):
			for c in range(currCol - 1, -1, -1):
				if arr[r][c] == 1:
					currCol = c
					currRow = r
				else:
					break
			if currCol == 0:
				break
		return currRow


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max = 0
		index = 0
		for i in range(n):
			(l, r) = (0, m - 1)
			if arr[i][r] == 0:
				continue
			while l <= r:
				mid = (l + r) // 2
				if arr[i][mid] == 0:
					l = mid + 1
				if arr[i][mid] == 1:
					r = mid - 1
			if m - r > max:
				index = i
				max = m - r
		if max == 0:
			return -1
		return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		c = 0
		for i in arr:
			if c < sum(i):
				c = sum(i)
		if c == 0:
			return -1
		else:
			for i in range(len(arr)):
				if sum(arr[i]) == c:
					return i


class Solution:

	def rowWithMax1s(self, arr, n, m):
		c = m - 1
		r_i = -1
		for i in range(n):
			while c >= 0 and arr[i][c] == 1:
				c -= 1
				r_i = i
		return r_i


class Solution:

	def rowWithMax1s(self, arr, n, m):
		count_arr = []
		for i in range(n):
			count = 0
			for j in range(m):
				if arr[i][j] == 1:
					count += 1
			count_arr.append(count)
		if max(count_arr) == 0:
			return -1
		max_ele = count_arr[0]
		index = 0
		for i in range(1, len(count_arr)):
			if count_arr[i] > max_ele:
				max_ele = count_arr[i]
				index = i
		return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		for i in range(m):
			for j in range(n):
				if arr[j][i] == 1:
					return j
		return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):

		def BinaryFirstSearch(arr):
			n = len(arr)
			(res, l, r) = (float('inf'), 0, n - 1)
			while l <= r:
				mid = (l + r) // 2
				if arr[mid] == 1:
					res = mid
					r = mid - 1
				else:
					l = mid + 1
			return res
		ans = []
		for (idx, num) in enumerate(arr):
			ans.append([BinaryFirstSearch(num), idx])
		if min(ans)[0] < float('inf'):
			return min(ans)[1]
		return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):

		def BinaryFirstSearch(arr):
			n = len(arr)
			(res, l, r) = (n, 0, n - 1)
			while l <= r:
				mid = (l + r) // 2
				if arr[mid] == 1:
					res = mid
					r = mid - 1
				else:
					l = mid + 1
			return res
		mx = 0
		ans = -1
		for i in range(len(arr)):
			if m - BinaryFirstSearch(arr[i]) > mx:
				mx = m - BinaryFirstSearch(arr[i])
				ans = i
		return ans


class Solution:

	def rowWithMax1s(self, matrix, n, m):
		res = []

		def leftocc(arr):
			start = 0
			end = len(arr) - 1
			mid = start + (end - start) // 2
			ans = 0
			while start <= end:
				if arr[mid] == 1:
					ans = mid
					end = mid - 1
				else:
					start = mid + 1
				mid = start + (end - start) // 2
			if ans == 0 and arr[0] == 0:
				return 0
			else:
				return len(arr) - ans
		for row in range(len(matrix)):
			count = leftocc(matrix[row])
			res.append((-1 * count, row))
		while True and res:
			ans = min(res)
			if ans[0] == 0:
				res.remove((ans[0], ans[1]))
			else:
				return ans[1]
		return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		l = []
		for i in range(n):
			x = arr[i].count(1)
			l.append(x)
		x = max(l)
		if x == 0:
			return -1
		else:
			return l.index(max(l))


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max = 0
		index = -1

		def bis(low, high, arr, c):
			mid = (low + high) // 2
			if low > high:
				return c
			if arr[mid] == 1:
				c += high - mid + 1
				return bis(low, mid - 1, arr, c)
			else:
				return bis(mid + 1, high, arr, c)
		for i in range(len(arr)):
			k = bis(0, m - 1, arr[i], 0)
			if max < k:
				max = k
				index = i
		return index


class Solution:

	def rowWithMax1s(self, matrix, R, C):
		row = -1
		j = C - 1
		for i in range(R):
			while j >= 0 and matrix[i][j] == 1:
				j -= 1
				row = i
		return row


class Solution:

	def rowWithMax1s(self, arr, n, m):
		dic = {}
		for (ind, row) in enumerate(arr):
			dic[ind] = row.count(1)
		maxvalue = 0
		index = 0
		for (key, value) in dic.items():
			if value > maxvalue:
				maxvalue = value
				index = key
		if maxvalue == 0:
			return -1
		return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		list_a = []
		k = 0
		for i in range(n):
			list_a.append(sum(arr[i]))
		max_count = max(list_a)
		for j in range(n):
			if max_count > 0:
				if max_count == list_a[j]:
					return j
		if k == 0:
			return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		(s, idx) = (-1, -1)
		for i in range(len(arr)):
			temp = sum(arr[i])
			if temp >= 1 and temp > s:
				s = temp
				idx = i
		return idx


class Solution:

	def rowWithMax1s(self, arr, n, m):
		l = 0
		maxx = 0
		index = -1
		for i in range(n):
			if arr[i][-1] == 1:
				l = 0
				if m == 1:
					l = 1
				for j in range(m - 1):
					if arr[i][j] < arr[i][j + 1] or arr[i][j] == 1:
						if j == 0 and arr[i][j] == 1:
							l = m
						else:
							l = m - 1 - j
						break
				if l == m:
					return i
				if l > maxx:
					maxx = l
					index = i
		return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		c = [i for i in arr]
		k = []
		for i in range(len(c)):
			k.append(sum(c[i]))
		j = max(k)
		if sum(k) == 0:
			return -1
		return k.index(j)


class Solution:

	def rowWithMax1s(self, arr, n, m):
		c = mc = 0
		x = -1
		for i in range(len(arr)):
			c = arr[i].count(1)
			if c > mc:
				mc = c
				x = i
		return x


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max_row_index = 0
		index = m - 1
		for i in range(n):
			flag = False
			while index >= 0 and arr[i][index] == 1:
				flag = True
				index -= 1
				if flag:
					max_row_index = i
		if max_row_index == 0 and arr[0][m - 1] == 0:
			return -1
		return max_row_index


from collections import *

class Solution:

	def rowWithMax1s(self, arr, n, m):
		dic = defaultdict(list)
		for i in range(len(arr)):
			dic[i] = arr[i].count(1)
		count = 0
		value = 0
		for (i, v) in dic.items():
			if v > value:
				value = v
				count = i
		if value == 0:
			return -1
		return count


class Solution:

	def rowWithMax1s(self, a, n, m):

		def getAns(a):
			l = 0
			h = len(a) - 1
			res = -1
			while l <= h:
				m = (l + h) // 2
				if a[m] == 1:
					res = m
					h = m - 1
				else:
					l = m + 1
			return res
		index = -1
		ans = m
		for i in range(n):
			x = getAns(a[i])
			if x < ans and x >= 0:
				ans = x
				index = i
		return index


class Solution:

	def rowWithMax1s(self, arr, n, m):
		n = len(arr)
		m = len(arr[0])
		maxRow = -1
		maxCount = 0
		for i in range(n):
			count = 0
			for j in range(m):
				if arr[i][j] == 1:
					count += 1
			if count > maxCount:
				maxCount = count
				maxRow = i
		return maxRow


class Solution(object):

	def rowWithMax1s(self, grid, n, m):
		(top, bottom) = (0, n - 1)
		(left, right) = (0, m - 1)
		result = -1
		while top <= bottom and left <= right:
			if grid[top][right] == 1:
				result = top
				right -= 1
			else:
				top += 1
		return result


class Solution:

	def rowWithMax1s(self, arr, n, m):
		(a, ac) = (-1, m)
		for i in range(n):
			(j, k) = (0, m - 1)
			while j <= k:
				mid = (j + k) // 2
				if arr[i][mid] == 1:
					k = mid - 1
				else:
					j = mid + 1
			ci = j
			if j < ac:
				a = i
				ac = j
		return a


class Solution:

	def rowWithMax1s(self, arr, n, m):
		(a, j) = (-1, m)
		for i in range(n):
			while j > 0 and arr[i][j - 1] == 1:
				a = i
				j -= 1
			if j == 0:
				return i
		return a


class Solution:

	def rowWithMax1s(self, arr, n, m):
		ans = []
		for i in range(n):
			s = 0
			for j in range(m):
				if arr[i][j] == 1:
					s += 1
			ans.append(s)
		ms = 0
		mi = -1
		for i in range(n):
			if ans[i] > ms:
				ms = ans[i]
				mi = i
		return mi


class Solution:

	def rowWithMax1s(self, arr, n, m):
		maxx = 0
		c = 0
		for i in range(len(arr)):
			if 1 not in arr[i]:
				c += 1
			if arr[i].count(1) > arr[maxx].count(1):
				maxx = i
		if c == len(arr):
			return -1
		return maxx


class Solution:

	def rowWithMax1s(self, arr, n, m):
		l = []
		for i in range(n):
			c = 0
			for j in range(m):
				if arr[i][j] == 1:
					c += 1
			l.append(c)
		maxi = max(l)
		if maxi != 0:
			return l.index(maxi)
		else:
			return -1


class Solution:

	def rowWithMax1s(self, arr, n, m):
		max_ones = 0
		row = -1
		for i in range(n):
			one_count = 0
			for j in range(m):
				if arr[i][j] == 1:
					one_count = m - j
					if one_count > max_ones:
						max_ones = one_count
						row = i
					break
		return row