Given a binary matrix (containing only 0 and 1) of order NxN. All rows are sorted already, We need to find the row number with the maximum number of 1s. Also, find the number of 1s in that row.
Note:
1. In case of a tie, print the smaller row number.
2. Row number should start from 0^{th} index.
Example 1
Input:
N=3
mat[3][3] = {0, 0, 1, 
              0, 1, 1, 
              0, 0, 0}
Output:
Row number = 1
MaxCount = 2
Explanation:
Here, max number of 1s is in row number 1
and its count is 2.
Example 2
Input:
N=3
mat[3][3] = {1, 1, 1, 
              1, 1, 1, 
              0, 0, 0}
Output:
Row number = 0
MaxCount = 3
Your Task:
You don't need to read input or print anything. The task is to complete the function findMaxRow() which takes mat[][] as the 2D matrix and N as the size of matrix. Your task is to find the row number with the maximum number of 1s and find the number of 1s in that row and return the answer in a vector of size 2 where at 0^{th }index will be the row number and at 1^{th }index will be MaxCount.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{3}
0 <= mat[][]<= 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3



class Solution:

    def findMaxRow(self, mat, N):

        # Code here

Solutions:
class Solution:

	def findMaxRow(self, mat, N):
		li = []
		for i in range(N):
			li.append(sum(mat[i]))
		key = max(li)
		for i in range(len(li)):
			if li[i] == key:
				return (i, key)


class Solution:

	def findMaxRow(self, mat, N):
		ans = [0, 0]
		for i in range(N):
			j = N - 1 - ans[-1]
			while mat[i][j] == 1 and j >= 0:
				ans[0] = i
				j -= 1
			ans[-1] = N - 1 - j
		return ans


class Solution:

	def findMaxRow(self, mat, N):
		max_count = 0
		max_row = 0
		for i in range(N):
			count = mat[i].count(1)
			if count > max_count:
				max_count = count
				max_row = i
		return [max_row, max_count]


class Solution:

	def findMaxRow(self, mat, N):
		maxx = 0
		j = int()
		for i in range(n):
			summ = sum(list(mat[i]))
			if summ > maxx:
				maxx = summ
				j = i
		return (j, maxx)


def getCount(arr, n):
	if arr[0] == 1:
		return n
	(st, en) = (0, n - 1)
	while st <= en:
		mid = (st + en) // 2
		if mid > 0 and arr[mid] == 1 and (arr[mid - 1] == 0):
			return n - mid
		if arr[mid] == 1:
			en = mid - 1
		else:
			st = mid + 1
	return 0

class Solution:

	def findMaxRow(self, mat, N):
		ans = [-1, -1]
		for i in range(N):
			temp = getCount(mat[i], N)
			if temp > ans[1]:
				ans[1] = temp
				ans[0] = i
		return ans


class Solution:

	def findMaxRow(self, mat, N):
		list1 = []
		list2 = []
		for i in range(N):
			list1.append((i, mat[i].count(1)))
		for i in list1:
			list2.append(i[1])
		m = max(list2)
		for i in list1:
			if m == i[1]:
				return [i[0], i[1]]


class Solution:

	def findMaxRow(self, mat, N):
		x = []
		for i in range(N):
			low = 0
			high = N - 1
			while low <= high:
				mid = (low + high) // 2
				if mat[i][mid] < 1:
					low = mid + 1
				else:
					high = mid - 1
			if N - low == N:
				return [i, N]
			x.append(N - low)
		return [x.index(max(x)), max(x)]


class Solution:

	def findMaxRow(self, mat, N):
		i = 0
		j = 0
		s = 0
		for row in mat:
			t = sum(row)
			if t > s:
				s = t
				i = j
			j += 1
		return [i, s]


class Solution:

	def findMaxRow(self, mat, N):
		max_row = 0
		max_count = 0
		i = 0
		j = N - 1
		while i < N and j >= 0:
			if mat[i][j] == 1:
				max_count += 1
				max_row = i
				j -= 1
			else:
				i += 1
		return [max_row, max_count]


class Solution:

	def findMaxRow(self, mat, N):
		ret = 0
		mn = float('inf')
		import bisect as bs
		for i in range(N):
			j = bs.bisect_left(mat[i], 1)
			if j < mn:
				mn = j
				ret = i
		return (ret, N - mn)


class Solution:

	def findMaxRow(self, mat, N):
		ret = 0
		mn = float('inf')
		for i in range(N):
			(l, r) = (0, N - 1)
			while l < r:
				m = l + (r - l) // 2
				if mat[i][m] == 0:
					l = m + 1
				else:
					r = m
			if mat[i][l] == 1 and l < mn:
				mn = l
				ret = i
		if mn == float('inf'):
			mn = N
		return (ret, N - mn)


class Solution:

	def findMaxRow(self, mat, N):
		count1 = 0
		row = 0
		for i in range(N):
			count2 = count1
			for j in range(N - count1 - 1, -1, -1):
				if mat[i][j] == 0:
					break
				count2 += 1
			if count2 > count1:
				count1 = count2
				row = i
		return (row, count1)


class Solution:

	def findMaxRow(self, mat, N):
		count = 0
		row = 0
		for i in range(N):
			present_count = mat[i].count(1)
			if present_count > count:
				count = present_count
				row = i
		return (row, count)


class Solution:

	def findMaxRow(self, mat, N):

		def bin(p):
			start = 0
			end = N - 1
			res = N + 1
			while start <= end:
				mid = (start + end) // 2
				if p[mid] == 1:
					res = min(res, mid)
					end = mid - 1
				else:
					start = mid + 1
			if res == N + 1:
				return 999999
			return res
		c = 0
		count = 0
		res = [0, 0]
		for i in mat:
			q = N - bin(i)
			if q > res[1]:
				res[0] = count
				res[1] = q
			count += 1
		return res


class Solution:

	def findMaxRow(self, mat, N):
		for i in range(N):
			sumOfrow = sum(mat[i])
			mat[i] = sumOfrow
		maxsum = max(mat)
		maxindex = mat.index(maxsum)
		ans = [maxindex, maxsum]
		return ans


class Solution:

	def findMaxRow(self, mat, N):
		ans = 0
		row = 0
		for i in range(N):
			count = 0
			for j in range(N - 1, -1, -1):
				if mat[i][j] != 1:
					break
				else:
					count += 1
			if count > row:
				row = count
				ans = i
		return [ans, row]


class Solution:

	def findMaxRow(self, mat, N):
		j = 0
		ans = [0, 0]
		sum1 = -1
		for i in mat:
			if sum1 < sum(i):
				ans[0] = j
				ans[1] = sum(i)
				sum1 = sum(i)
			j = j + 1
		return ans


class Solution:

	def findMaxRow(self, mat, N):
		rn = 0
		mc = 0
		tmc = 0
		trn = 0
		for i in range(0, N):
			if mat[i][0] == 1:
				rn = i
				mc = N
				break
			else:
				if 1 in mat[i]:
					tmc = N - mat[i].index(1)
					trn = i
				if mc < tmc:
					mc = tmc
					rn = trn
		z = []
		z.append(rn)
		z.append(mc)
		return z


class Solution:

	def findMaxRow(self, mat, N):
		(rowNumber, maxCount) = (0, 0)
		for i in range(N):
			rowCount = maxCount
			for j in range(N - maxCount - 1, -1, -1):
				if mat[i][j] == 0:
					break
				rowCount += 1
			if rowCount > maxCount:
				maxCount = rowCount
				rowNumber = i
			if maxCount == N:
				break
		return (rowNumber, maxCount)


class Solution:

	def findMaxRow(self, mat, N):
		lst = []
		for row in mat:
			countRow = row.count(1)
			lst.append(countRow)
		max_count = max(lst)
		row_number = lst.index(max_count)
		return [row_number, max_count]


class Solution:

	def findMaxRow(self, mat, N):
		(x, y) = (0, 0)
		for i in range(N):
			rc = y
			for j in range(N - y - 1, -1, -1):
				if mat[i][j] == 0:
					break
				rc += 1
			if rc > y:
				y = rc
				x = i
			if y == N:
				break
		return (x, y)


class Solution:

	def findMaxRow(self, mat, N):
		maxcount = 0
		row = 0
		col = N - 1
		s = 0
		while row < N and col >= 0:
			if mat[row][col] == 1:
				s = row
				maxcount += 1
				col -= 1
			else:
				row += 1
		return [s, maxcount]


class Solution:

	def findMaxRow(self, mat, N):
		N = len(mat)
		max_ones = 0
		max_row = 0
		for i in range(N):
			ones = mat[i].count(1)
			if ones > max_ones:
				max_ones = ones
				max_row = i
		return (max_row, max_ones)


class Solution:

	def findMaxRow(self, mat, N):
		ans = 0
		count = mat[0].count(1)
		for i in range(N):
			t = mat[i].count(1)
			if t > count:
				ans = i
				count = t
		return [ans, count]


class Solution:

	def findMaxRow(self, mat, n):
		(i, j) = (0, n - 1)
		(row, count) = (0, 0)
		while i < n and j >= 0:
			if mat[i][j] == 1:
				row = i
				count += 1
				j -= 1
			else:
				i += 1
		return [row, count]


class Solution:

	def findMaxRow(self, mat, N):
		ans = 0
		max_count = 0
		for i in range(N):
			count = 0
			l = 0
			h = N - 1
			while l <= h:
				mid = (l + h) // 2
				if mat[i][mid] == 0:
					l = mid + 1
				elif mat[i][mid] >= 1:
					h = mid - 1
			if N - l > max_count:
				max_count = N - l
				ans = i
		return (ans, max_count)


class Solution:

	def findMaxRow(self, mat, N):
		mc = 0
		ind = 0
		for i in range(len(mat)):
			x = mat[i].count(1)
			if x > mc:
				mc = x
				ind = i
		return [ind, mc]


class Solution:

	def findMaxRow(self, mat, N):
		row = 0
		number_of_one = 0
		for i in range(N):
			try:
				a = mat[i].index(1)
				if n - a > number_of_one:
					number_of_one = n - a
					row = i
			except:
				continue
		return (row, number_of_one)


class Solution:

	def findMaxRow(self, mat, N):
		cm = 0
		rn = 0
		for i in range(N):
			rc = cm
			for j in range(N - cm - 1, -1, -1):
				if mat[i][j] == 1:
					rc += 1
				else:
					break
			if rc > cm:
				cm = rc
				rn = i
			if cm == N:
				break
		return (rn, cm)


class Solution:

	def findMaxRow(self, mat, N):
		min_row = float('inf')
		max_count = float('-inf')
		for r in range(N):
			row_sum = sum(mat[r])
			if row_sum > max_count:
				max_count = row_sum
				min_row = r
		return (min_row, max_count)


import math

class Solution:

	def findMaxRow(self, mat, N):
		(i, j) = (0, N - 1)
		(maxi, maxind) = (0, 0)
		while j >= 0 and i < N:
			if mat[i][j] == 1:
				maxi += 1
				maxind = i
				j -= 1
			else:
				i += 1
		return (maxind, maxi)


class Solution:

	def findMaxRow(self, mat, N):
		start_row = 0
		ans = [0, 0]
		start_col = N - 1
		while start_row <= N - 1 and start_col >= 0:
			if mat[start_row][start_col] == 0:
				start_row += 1
			elif mat[start_row][start_col] == 1:
				ans[0] = start_row
				ans[1] += 1
				start_col -= 1
		return ans


class Solution:

	def findMaxRow(self, mat, N):
		(Rn, Mc) = (0, 0)
		for i in range(N):
			SUM = sum(mat[i])
			if SUM > Mc:
				(Mc, Rn) = (SUM, i)
		return (Rn, Mc)


class Solution:

	def findMaxRow(self, mat, n):
		(maxr, maxc) = (0, 0)
		for i in range(n):
			maxn = maxc
			for j in range(n - maxc - 1, -1, -1):
				if mat[i][j] == 0:
					break
				maxn += 1
			if maxn > maxc:
				maxc = maxn
				maxr = i
			if maxc == n:
				break
		return (maxr, maxc)


class Solution:

	def findMaxRow(self, mat, N):
		maxC = 0
		ans = 0
		for i in range(N):
			if mat[i][0] == 1:
				return [i, N]
			if mat[i][N - 1] == 0:
				continue
			s = 0
			e = N - 1
			while s <= e:
				mid = (s + e) // 2
				if mat[i][mid] == 1 and mat[i][mid - 1] == 0:
					count = N - mid
					if count > maxC:
						maxC = count
						ans = i
						break
				if mat[i][mid] == 1:
					e = mid - 1
				else:
					s = mid + 1
		return [ans, maxC]


class Solution:

	def findMaxRow(self, mat, N):
		dict1 = {}
		max1 = 0
		for i in range(N):
			a = mat[i]
			if 1 in a:
				c = a.count(1)
				if c > max1:
					max1 = c
					if max1 not in dict1:
						dict1[max1] = [i]
					else:
						dict1[max1].append(i)
				elif c not in dict1:
					dict1[c] = [i]
				else:
					dict1[c].append(i)
			else:
				continue
		if len(dict1) == 0:
			return [0, 0]
		max2 = 0
		for i in dict1.keys():
			if i > max2:
				max2 = i
		ind = min(dict1[max2])
		return [ind, max2]


class Solution:

	def findMaxRow(self, arr, N):

		def bsearch(arr, low, high):
			if arr[low] == 1:
				return high + 1
			elif arr[high] == 0:
				return 0
			while low <= high:
				mid = (low + high) // 2
				if mid + 1 < N and arr[mid] == 0 and (arr[mid + 1] == 1):
					return N - mid - 1
				elif mid - 1 >= 0 and arr[mid] == 1 and (arr[mid - 1] == 0):
					return N - mid
				elif arr[mid] == 0:
					low = mid + 1
				elif arr[mid] == 1:
					high = mid - 1
		maximum = 0
		nth_row = 0
		for i in range(N):
			value = bsearch(arr[i], 0, N - 1)
			if value > maximum:
				maximum = value
				nth_row = i
		return (nth_row, maximum)


class Solution:

	def findMaxRow(self, mat, N):
		max_no_1s = 0
		row_index = 0
		for arr_index in range(len(mat)):
			arr = mat[arr_index]
			count = 0
			no_of_1s = 0
			for i in arr:
				if i == 0:
					count += 1
				else:
					no_of_1s = len(arr) - count
					break
			if no_of_1s > max_no_1s:
				max_no_1s = no_of_1s
				row_index = arr_index
		return [row_index, max_no_1s]


class Solution:

	def findMaxRow(self, mat, N):
		ans = -1
		track = 0
		real_ans = []
		for x in mat:
			temp = sum(x)
			if ans < temp:
				ans = temp
				real_ans = [track, ans]
			track += 1
		return real_ans


class Solution:

	def findMaxRow(self, mat, N):
		(m1, mi) = (0, 0)
		for i in range(len(mat)):
			count = mat[i].count(1)
			if count > m1:
				mi = i
				m1 = count
		return [mi, m1]


class Solution:

	def findMaxRow(self, mat, N):
		(row, max_count) = (0, 0)
		j = N - 1
		for i in range(N):
			while j >= 0 and mat[i][j] == 1:
				j -= 1
				row = i
			if j == -1:
				break
		for i in range(N):
			if mat[row][i] == 1:
				max_count += 1
		return [row, max_count]


class Solution:

	def findMaxRow(self, mat, N):
		(mr, mo) = (0, 0)
		for i in range(len(mat)):
			x = mat[i].count(1)
			if x > mo:
				mr = i
				mo = x
		return [mr, mo]


class Solution:

	def findMaxRow(self, mat, N):
		maxx = N
		row = 0
		rows = 0
		for i in mat:
			count = 0
			for j in i:
				if j == 0:
					count += 1
				else:
					break
			if count < maxx:
				maxx = count
				rows = row
			row += 1
		return [rows, N - maxx]


class Solution:

	def findMaxRow(self, mat, N):
		rc = 0
		mxCnt = 0
		cnt = 0
		for i in range(N):
			cnt = 0
			for j in range(N - 1, -1, -1):
				if mat[i][j] == 0:
					break
				cnt += 1
			if cnt > mxCnt:
				mxCnt = cnt
				rc = i
			if mxCnt > N:
				break
		return (rc, mxCnt)


class Solution:

	def findMaxRow(self, mat, N):
		sumrow = index = 0
		for i in range(N):
			if sumrow < sum(mat[i]):
				sumrow = sum(mat[i])
				index = i
		return (index, sumrow)


class Solution:

	def findMaxRow(self, mat, N):
		l = []
		for i in mat:
			l.append(i.count(1))
		return (l.index(max(l)), max(l))


class Solution:

	def findMaxRow(self, mat, N):
		cnt = 0
		n = 0
		for i in range(N):
			if mat[i].count(1) > cnt:
				cnt = mat[i].count(1)
				n = i
		return [n, cnt]


class Solution:

	def findMaxRow(self, mat, N):
		i = 0
		j = N - 1
		countone = 0
		row = 0
		while j >= 0 and i < N:
			if mat[i][j] == 1:
				countone += 1
				row = i
				j -= 1
			else:
				i += 1
		return (row, countone)


class Solution:

	def findMaxRow(self, mat, N):
		ans = 0
		ansi = 0
		for i in range(N):
			temp = sum(mat[i])
			if temp > ans:
				ans = temp
				ansi = i
			if ans == N:
				return (i, N)
		return (ansi, ans)


class Solution:

	def findMaxRow(self, mat, N):
		(x, y) = (0, N - 1)
		ans = [0, 0]
		while x < N and y >= 0:
			if mat[x][y] == 1:
				if N - y > ans[1]:
					ans[0] = x
					ans[1] = N - y
				y -= 1
			else:
				x += 1
		return (ans[0], ans[1])


class Solution:

	def findMaxRow(self, mat, N):
		max_ones = 0
		row_number = 0
		for i in range(len(mat)):
			ones = sum(mat[i])
			if max_ones < ones:
				max_ones = ones
				row_number = i
		return (row_number, max_ones)


class Solution:

	def findMaxRow(self, mat, N):
		max_sum = float('-inf')
		max_row = -1
		for i in range(N):
			row_sum = sum(mat[i])
			if row_sum > max_sum:
				max_sum = row_sum
				max_row = i
		return [max_row, max_sum]


class Solution:

	def findMaxRow(self, mat, N):
		(x, y) = (0, 0)
		for i in range(len(mat)):
			c = 0
			for j in mat[i]:
				if j == 1:
					c += 1
			if c > x:
				x = c
				y = i
		return (y, x)


class Solution:

	def findMaxRow(self, mat, N):
		(m, n) = (0, 0)
		for i in range(len(mat)):
			c = 0
			for j in mat[i]:
				if j == 1:
					c += 1
			if c > m:
				m = c
				n = i
		return (n, m)


class Solution:

	def findMaxRow(self, mat, N):
		minIndex = N
		row = 0
		for r in range(N):
			if 1 in mat[r]:
				if mat[r].index(1) < minIndex:
					minIndex = mat[r].index(1)
					row = r
		return (row, N - minIndex)


class Solution:

	def findMaxRow(self, mat, N):
		index = N
		max_row = 0
		max_1s = 0
		i = N - 1
		while i >= 0:
			if mat[0][i] == 0:
				break
			else:
				index = i
				max_1s = max_1s + 1
				i = i - 1
		for j in range(N - 1):
			if index > 0 and mat[j + 1][index - 1] == 1:
				max_row = j + 1
				index = index - 1
				max_1s = max_1s + 1
				while index > 0 and mat[j + 1][index - 1] == 1:
					index = index - 1
					max_1s = max_1s + 1
		ans = [max_row, max_1s]
		return ans


class Solution:

	def findMaxRow(self, mat, N):
		lst = []
		bst = []
		for i in range(len(mat)):
			a = mat[i]
			b = a.count(1)
			lst.append(i)
			bst.append(b)
		c = max(bst)
		for i in range(len(bst)):
			if bst[i] == c:
				return (lst[i], bst[i])


class Solution:

	def findMaxRow(self, mat, N):
		rowNum = 0
		maxCount = 0
		for i in range(N):
			currCount = maxCount
			for j in range(N - maxCount - 1, -1, -1):
				if mat[i][j] == 0:
					break
				currCount += 1
			if currCount > maxCount:
				maxCount = currCount
				rowNum = i
			if maxCount == N:
				break
		return (rowNum, maxCount)


class Solution:

	def findMaxRow(self, mat, N):
		mapcallback = lambda row: row.count(1)
		counts = list(map(mapcallback, mat))
		return [counts.index(max(counts)), max(counts)]


class Solution:

	def findMaxRow(self, mat, N):
		ls = []
		m = 0
		I = 0
		s = 0
		for i in range(0, N):
			c = 0
			for j in range(0, N):
				if mat[i][j] == 0:
					c += 1
				else:
					break
			s = N - c
			if m < s:
				m = s
				I = i
			s = 0
		ls.append(I)
		ls.append(m)
		return ls


class Solution:

	def findMaxRow(self, mat, N):
		d = [0, 0]
		for i in range(len(mat)):
			t = sum(mat[i])
			if t > d[1]:
				d = [i, t]
		return d


class Solution:

	def findMaxRow(self, mat, N):
		r = 0
		count = 0
		for i in range(0, N):
			if count < mat[i].count(1):
				count = mat[i].count(1)
				r = i
		l = []
		l.append(r)
		l.append(count)
		return l


class Solution:

	def findMaxRow(self, mat, N):
		R = mat[0]
		(rn, rm) = (-1, 0)
		for r in mat:
			rn += 1
			if r.count(1) > R.count(1):
				rm = rn
				R = r
		return [rm, R.count(1)]


class Solution:

	def findMaxRow(self, mat, N):
		for y in range(N):
			for x in range(N):
				if mat[x][y] == 1:
					return [x, N - y]
		return [0, 0]


class Solution:

	def findMaxRow(self, mat, N):
		row = 0
		maxCount = 0
		for i in range(N):
			count = 0
			for j in range(N):
				if mat[i][j] == 1:
					count = N - j
					break
			if maxCount < count:
				maxCount = count
				row = i
		list = []
		list.append(row)
		list.append(maxCount)
		return list


class Solution:

	def findMaxRow(self, mat, N):
		l = []
		max = 0
		cnt = 0
		for i in range(N):
			if mat[i].count(1) > cnt:
				max = i
				cnt = mat[i].count(1)
		l.extend([max, cnt])
		return l