Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
Example 1:
Input:
N = 3, M = 4
Mat[] = {{0 1 1 1},
         {0 0 1 1},
         {0 0 1 1}}
Output: 0
Explanation: Row 0 has 3 ones whereas
rows 1 and 2 have just 2 ones.
Example 2:
Input: 
N = 2, M = 2
Mat[] = {{0 1},
         {1 1}}
Output: 1
Explanation: Row 1 has 2 ones whereas
row 0 has just a single one. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxOnes () which takes a 2D array Mat[][] and its dimensions N and M as inputs and returns the row index with the maximum number of 1s (0-based index). If there are multiple rows with the maximum number of ones, then return the row with the smaller index.
Expected Time Complexity: O(NLogM).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N, M <= 40
0 <= M[ ][ ] <= 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Matrices

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def maxOnes (self, Mat, N, M):

        # code here 



Solutions:
class Solution:

	def maxOnes(self, Mat, N, M):
		max = 0
		for i in range(N):
			c = 0
			for j in range(M):
				if Mat[i][j] == 1:
					c += 1
			if c > max:
				max = c
				ans = i
		return ans


from collections import Counter

class Solution:

	def maxOnes(self, mat, N, M):
		m = 0
		for i in range(len(mat)):
			d = Counter(mat[i])
			if d[1] > m:
				m = d[1]
				ind = i
		return ind


class Solution:

	def maxOnes(self, a, n, m):
		res = n
		k = 0
		for i in range(n):
			t = a[i].count(1)
			if t > k:
				k = t
				res = i
		return res


class Solution:

	def maxOnes(self, Mat, N, M):
		solution = []
		for i in Mat:
			solution.append(countNumberOfOnes(i))
		return solution.index(sorted(solution)[N - 1])

def countNumberOfOnes(arr):
	counter = 0
	for i in arr:
		if i == 1:
			counter += 1
	return counter


class Solution:

	def maxOnes(self, Mat, N, M):
		l = []
		for i in Mat:
			l.append(i.count(1))
		c = l.index(max(l))
		return c


class Solution:

	def maxOnes(self, Mat, N, M):
		k = []
		for i in range(N):
			k.append(Mat[i].count(1))
		if max(k) == 0:
			return -1
		else:
			return k.index(max(k))


class Solution:

	def maxOnes(self, Mat, N, M):
		ans = 0
		ind = M - 1
		for i in range(0, N):
			while ind >= 0 and Mat[i][ind] == 1:
				ind -= 1
				ans = i
		return ans


class Solution:

	def maxOnes(self, Mat, N, M):
		a = 0
		p = 0
		for i in range(N):
			c = 0
			for j in range(M):
				if Mat[i][M - j - 1] == 1:
					c += 1
				else:
					break
			if c > a:
				a = c
				p = i
		return p


class Solution:

	def maxOnes(self, Mat, N, M):
		index = -1
		maxi = -1000000000.0
		for i in range(N):
			count = 0
			for j in range(M):
				if Mat[i][j] == 1:
					count += 1
			if count > maxi:
				maxi = count
				index = i
		return index


class Solution:

	def maxOnes(self, Mat, N, M):
		si = -100
		more = -100
		for i in range(N):
			c = 0
			for j in range(M):
				if Mat[i][j] == 1:
					c += 1
			if c > more:
				more = c
				si = i
		return si


class Solution:

	def maxOnes(self, Mat, N, M):
		a = []
		for i in Mat:
			n = 0
			for j in i:
				if j == 1:
					n += 1
			a.append(n)
		m = a.index(max(a))
		return m


class Solution:

	def maxOnes(self, Mat, N, M):
		dict1 = {}
		for i in range(N):
			count = 0
			for j in range(M):
				if Mat[i][j] == 1:
					count += 1
				dict1[i] = count
		max1 = max(dict1, key=lambda k: dict1[k])
		return max1


class Solution:

	def maxOnes(self, Mat, N, M):
		max_row = -1
		max_ones = -1
		for i in range(N):
			left = 0
			right = M - 1
			while left <= right:
				mid = (left + right) // 2
				if Mat[i][mid] == 1:
					right = mid - 1
				else:
					left = mid + 1
			ones = M - left
			if ones > max_ones:
				max_ones = ones
				max_row = i
		return max_row


class Solution:

	def maxOnes(self, Mat, N, M):
		max_row_index = 0
		max = -1
		for i in range(N):
			index = self.first(Mat[i], 0, M - 1)
			if index != -1 and M - index > max:
				max = M - index
				max_row_index = i
		return max_row_index

	def first(self, 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 self.first(arr, mid + 1, high)
			else:
				return self.first(arr, low, mid - 1)
		return -1


class Solution:

	def maxOnes(self, Mat, N, M):
		max_row_index = 0
		max_ones = 0
		for i in range(N):
			count_ones = Mat[i].count(1)
			if count_ones > max_ones:
				max_ones = count_ones
				max_row_index = i
		return max_row_index


class Solution:

	def maxOnes(self, Mat, N, M):
		max_count = 0
		max_row = -1
		for i in range(N):
			count = Mat[i].count(1)
			if count > max_count:
				max_count = count
				max_row = i
		return max_row


class Solution:

	def maxOnes(self, mat, n, m):
		d = []
		for i in range(n):
			c = 0
			for j in range(m):
				if mat[i][j] == 1:
					c += 1
			d.append(c)
		mx = max(d)
		for i in range(len(d)):
			if d[i] == mx:
				return i


class Solution:

	def maxOnes(self, Mat, N, M):
		l = []
		for i in range(0, N):
			a = Mat[i]
			b = sum(a)
			l.append(b)
		c = l.index(max(l))
		return c


class Solution:

	def maxOnes(self, Mat, N, M):
		count = float('inf')
		loc = -1
		for i in range(len(Mat)):
			temp = 0
			for j in Mat[i]:
				if j == 1:
					break
				if j == 0:
					temp += 1
			if temp < count:
				count = temp
				loc = i
		return loc


class Solution:

	def maxOnes(self, Mat, N, M):
		maxm = 0
		ans = 0
		for i in range(N):
			s = 0
			for j in range(M):
				s += Mat[i][j]
			if s > maxm:
				maxm = s
				ans = i
		return ans


class Solution:

	def maxOnes(self, Mat, N, M):
		maxi = 0
		for i in range(N):
			count = Mat[i].count(1)
			if count > maxi:
				maxi = count
				ind = i
		return ind


class Solution:

	def maxOnes(self, Mat, N, M):
		d = []
		for i in range(N):
			c = 0
			for j in range(M):
				if Mat[i][j] == 1:
					c += 1
			d.append(c)
		mx = max(d)
		for i in range(len(d)):
			if d[i] == mx:
				return i


class Solution:

	def maxOnes(self, Mat, N, M):
		max = 0
		index = 0
		for i in range(N):
			c = 0
			for j in range(M):
				if Mat[i][j] == 1:
					c += 1
				elif Mat[i][j] > 1:
					break
			if c > max:
				max = c
				index = i
		return index


class Solution:

	def maxOnes(self, Mat, N, M):
		count_list = []
		for i in range(N):
			count = 0
			for j in range(M):
				if Mat[i][j] == 1:
					count += 1
			count_list.append(count)
		return count_list.index(max(count_list))


class Solution:

	def maxOnes(self, Mat, N, M):
		maxrow = 0
		index = M - 1
		flag = True
		for i in range(0, N):
			while index >= 0 and Mat[i][index] == 1:
				flag = True
				index = index - 1
				if flag:
					maxrow = i
			if maxrow == 0 and Mat[0][M - 1] == 0:
				return 0
		return maxrow


class Solution:

	def maxOnes(self, Mat, N, M):
		c = mc = 0
		x = -1
		for i in range(len(Mat)):
			c = Mat[i].count(1)
			if c > mc:
				mc = c
				x = i
		return x


class Solution:

	def maxOnes(self, Mat, N, M):
		l = [[sum(Mat[i]), i] for i in range(N)]
		e = max(l)[0]
		for i in l:
			if i[0] == e:
				return i[1]


class Solution:

	def maxOnes(self, Mat, N, M):
		maxones = 0
		maxrow = 0
		for (j, row) in enumerate(Mat):
			for (i, item) in enumerate(row):
				if item == 1:
					if M - i - 1 > maxones:
						maxrow = j
						maxones = M - i - 1
					break
		return maxrow


class Solution:

	def maxOnes(self, Mat, N, M):
		cnt = 0
		summ = Mat[0].count(1)
		for i in range(1, N):
			if Mat[i].count(1) > summ:
				cnt = i
				summ = Mat[i].count(1)
		return cnt


class Solution:

	def maxOnes(self, Mat, N, M):
		j = []
		for i in Mat:
			j.append(sum(i))
		max = j[0]
		for x in j:
			if x > max:
				max = x
		return j.index(max)


class Solution:

	def maxOnes(self, Mat, N, M):
		maxi = float('-inf')
		ans = 0
		for (i, j) in enumerate(Mat):
			if j.count(1) > maxi:
				maxi = j.count(1)
				ans = i
		return ans


class Solution:

	def maxOnes(self, Mat, N, M):
		list1 = []
		for i in range(N):
			row_count = 0
			for j in range(M):
				if int(Mat[i][j]) == 1:
					row_count += 1
			list1.append(row_count)
		maxnumber = 0
		index = 0
		for i in range(len(list1)):
			if list1[i] > maxnumber:
				maxnumber = list1[i]
				index = i
		return index


class Solution:

	def maxOnes(self, a, N, M):
		max = 0
		k = 0
		for i in range(N):
			c = 0
			for j in range(M):
				if a[i][j] == 1:
					c += 1
			if c > max:
				max = c
				k = i
		return k


class Solution:

	def maxOnes(self, Mat, N, M):
		maax = 0
		for row in range(N):
			max1 = 0
			for col in range(M):
				if Mat[row][col] == 1:
					max1 += 1
			if maax < max1:
				pos = row
				maax = max1
		return pos


class Solution:

	def maxOnes(self, Mat, N, M):
		max_sum = 0
		sum = 0
		for i in range(N):
			sum = 0
			for j in range(M):
				if Mat[i][j] == 1:
					sum += 1
			if sum > max_sum:
				max_sum = sum
				index = i
		return index


class Solution:

	def maxOnes(self, Mat, N, M):
		if N == 0 or M == 0:
			return -1
		max_count = -100000000.0
		memo = [0] * N
		for i in range(N):
			count = 0
			for j in range(M):
				if Mat[i][j] == 1:
					count += 1
			if count > max_count:
				max_count = count
				memo[i] = max_count
		return memo.index(max_count)


class Solution:

	def maxOnes(self, Mat, N, M):
		for i in range(0, M):
			for j in range(0, N):
				if Mat[j][i] == 1:
					return j
		else:
			return 0


class Solution:

	def maxOnes(self, Mat, N, M):
		res = 0
		resrow = 0
		for i in range(N):
			temp = 0
			for j in range(M):
				if Mat[i][j] == 1:
					temp += 1
			if res < temp:
				res = temp
				resrow = i
		return resrow


class Solution:

	def maxOnes(self, Mat, N, M):
		arr = []
		for i in range(N):
			count = 0
			for j in range(M):
				if Mat[i][j] == 1:
					count += 1
			arr.append(count)
		maxi = max(arr)
		for i in range(len(arr)):
			if arr[i] == maxi:
				return i


class Solution:

	def maxOnes(self, Mat, N, M):
		max = 0
		id = 0
		S = 0
		for k in range(N):
			for i in range(M):
				S += Mat[k][i]
			if S > max:
				max = S
				id = k
			S = 0
		return id


class Solution:

	def maxOnes(self, mat, N, M):
		if not mat or not len(mat):
			return
		row = -1
		(i, j) = (0, len(mat[0]) - 1)
		while i <= len(mat) - 1 and j >= 0:
			if mat[i][j] == 1:
				j = j - 1
				row = i
			else:
				i = i + 1
		return row


class Solution:

	def maxOnes(self, Mat, N, M):
		max_cnt = 0
		ans = 0
		for i in range(N):
			cnt = 0
			for j in range(M):
				if Mat[i][j] == 1:
					cnt += 1
			if cnt > max_cnt:
				ans = i
				max_cnt = cnt
		return ans


class Solution:

	def maxOnes(self, Mat, N, M):
		cnt_arr = []
		for i in range(N):
			cnt = 0
			for j in range(M):
				if Mat[i][j] == 1:
					cnt += 1
			cnt_arr.append(cnt)
		max_cnt = max(cnt_arr)
		for i in range(len(cnt_arr)):
			if cnt_arr[i] == max_cnt:
				return i


class Solution:

	def maxOnes(self, Mat, N, M):
		for i in range(N):
			Mat[i] = sum(Mat[i])
		return Mat.index(max(Mat))


class Solution:

	def maxOnes(self, Mat, N, M):
		ma = Mat[0].count(1)
		ans = 0
		for i in range(1, N):
			t = Mat[i].count(1)
			if t > ma:
				ma = t
				ans = i
		return ans


class Solution:

	def maxOnes(self, a, N, M):
		b = []
		for i in a:
			c = 0
			for j in i:
				if j == 1:
					c = c + 1
			b.append(c)
		return b.index(max(b))


class Solution:

	def maxOnes(self, Mat, N, M):
		arr = []
		for i in range(N):
			arr.append(Mat[i].count(1))
		return arr.index(max(arr))


class Solution:

	def maxOnes(self, Mat, N, M):
		count = 0
		flag = 0
		suma = 0
		for i in range(N):
			sum = 0
			for j in range(M):
				sum += Mat[i][j]
			if sum > suma:
				suma = sum
				count = i
		return count


class Solution:

	def maxOnes(self, Mat, N, M):
		arr = []
		for i in Mat:
			arr.append(sum(i))
		return arr.index(max(arr))


class Solution:

	def maxOnes(self, Mat, N, M):
		from collections import Counter
		HIGH = 0
		result = 0
		for i in range(N):
			li = Mat[i]
			TV = Counter(li)
			if TV[1] > HIGH:
				HIGH = TV[1]
				result = i
		return result


class Solution:

	def maxOnes(self, Mat, N, M):
		dict1 = {}
		lst = []
		for i in range(N):
			count = 0
			for j in range(M):
				if Mat[i][j] == 1:
					count += 1
			dict1[i] = count
		for values in dict1:
			x = max(dict1.values())
			for (key, values) in dict1.items():
				if values == x:
					return key


class Solution:

	def maxOnes(self, Mat, N, M):
		sm = -1
		r = None
		for i in range(N):
			if sum(Mat[i][:]) > sm:
				r = i
				sm = sum(Mat[i][:])
		return r


class Solution:

	def maxOnes(self, Mat, N, M):
		l = []
		c = 0
		for i in Mat:
			for j in i:
				if j == 1:
					c += 1
			l.append(c)
			c = 0
		return l.index(max(l))


class Solution:

	def maxOnes(self, Mat, N, M):
		res = [0, Mat[0].count(1)]
		for i in range(1, len(Mat)):
			ct = Mat[i].count(1)
			if ct > res[1]:
				(res[0], res[1]) = (i, ct)
		return res[0]


class Solution:

	def maxOnes(self, Mat, N, M):
		i = 0
		j = M - 1
		while i < N and j >= 0:
			if Mat[i][j] == 1:
				maxRow = i
				j -= 1
			else:
				i += 1
		return maxRow


class Solution:

	def maxOnes(self, Mat, N, M):
		r = 999
		maxi = 0
		for i in range(N):
			c = 0
			j = M - 1
			while j >= 0 and Mat[i][j] == 1:
				c += 1
				j -= 1
			if c > maxi:
				maxi = c
				r = i
		return r


class Solution:

	def maxOnes(self, Mat, N, M):
		max_sum = -1
		ind = -1
		for i in range(len(Mat)):
			j = sum(Mat[i])
			if j > max_sum:
				max_sum = max(max_sum, j)
				ind = i
		return ind


class Solution:

	def maxOnes(self, Mat, N, M):
		maxOnesRow = 0
		rowNumber = -1
		for i in range(N):
			count = 0
			for j in range(M):
				if Mat[i][j] == 1:
					count += 1
			if count > maxOnesRow:
				maxOnesRow = count
				rowNumber = i
		return rowNumber


class Solution:

	def maxOnes(self, Mat, N, M):
		max = 0
		curr_max = 0
		max_1 = -1
		for i in range(N):
			s = 0
			e = M - 1
			mini = M
			mid = 0
			while s <= e:
				mid = (s + e) // 2
				if Mat[i][mid] == 1:
					mini = mid
					e = mid - 1
				elif Mat[i][mid] < 1:
					s = mid + 1
				else:
					e = mid - 1
			curr_max = M - mini
			if curr_max > max:
				max = curr_max
				max_1 = i
		return max_1


class Solution:

	def maxOnes(self, Mat, N, M):
		ones = 0
		res = 0
		for i in range(N):
			temp = Mat[i].count(1)
			if temp > ones:
				ones = temp
				res = i
		return res


class Solution:

	def maxOnes(self, Mat, N, M):
		list1 = list()
		for i in Mat:
			list1.append(i.count(1))
		if max(list1) == 0:
			return -1
		return list1.index(max(list1))


class Solution:

	def maxOnes(self, Mat, N, M):
		s = 0
		k = 0
		for i in range(N):
			Mat[i] = sum(Mat[i])
			if Mat[i] > s:
				k = i
				s = max(Mat[i], s)
		return k


class Solution:

	def maxOnes(self, Mat, N, M):
		m = 0
		k = 0
		for i in range(N):
			c = 0
			for j in range(M):
				if Mat[i][j] == 1:
					c += 1
			if c > m:
				m = c
				k = i
		return k


class Solution:

	def maxOnes(self, Mat, N, M):
		arr = []
		count = 0
		for i in range(N):
			count = sum(Mat[i])
			arr.append(count)
			count = 0
		for k in range(len(arr)):
			if arr[k] == max(arr):
				return k
				break