Given a matrix mat of size R*C with 0 and 1s, find the largest rectangle of all 1s in the matrix. The rectangle can be formed by swapping any pair of columns of given matrix.
Example 1:
Input: 
R = 3, C = 5
mat[][] = {{0, 1, 0, 1, 0},
           {0, 1, 0, 1, 1},
           {1, 1, 0, 1, 0}};
Output: 6
Explanation: The largest rectangle's area
is 6. The rectangle can be formed by
swapping column  2 with 3. The matrix
after swapping will be
     0 0 1 1 0
     0 0 1 1 1
     1 0 1 1 0
Example 2:
Input:
R = 4, C = 5
mat[][] = {{0, 1, 0, 1, 0},
           {0, 1, 1, 1, 1},
           {1, 1, 1, 0, 1},
           {1, 1, 1, 1, 1}};
Output: 9
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxArea() which takes the 2D array of booleans mat, r and c as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(R*(R + C))
Expected Auxiliary Space: O(R*C)
Constraints:
1<= R,C <=10^{3}
0 <= mat[i][j] <= 1

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Starter code: #User function Template for python3

class Solution:



	def maxArea(self,mat, r, c):

		# code here

Solutions:
class Solution:

	def maxArea(self, mat, r, c):
		hist = [[0 for _ in range(c)] for _ in range(r)]
		for j in range(c):
			hist[0][j] = mat[0][j]
		for i in range(1, r):
			for j in range(c):
				if mat[i][j]:
					hist[i][j] = hist[i - 1][j] + mat[i][j]
		for i in range(r):
			hist[i].sort(reverse=True)
		ans = 0
		for i in range(r):
			for j in range(c):
				ans = max(ans, hist[i][j] * (j + 1))
		return ans


class Solution:

	def maxArea(self, mat, R, C):
		hist = [[0 for i in range(C + 1)] for i in range(R + 1)]
		for i in range(0, C, 1):
			hist[0][i] = mat[0][i]
			for j in range(1, R, 1):
				if mat[j][i] == 0:
					hist[j][i] = 0
				else:
					hist[j][i] = hist[j - 1][i] + 1
		for i in range(0, R, 1):
			count = [0 for i in range(R + 1)]
			for j in range(0, C, 1):
				count[hist[i][j]] += 1
			col_no = 0
			j = R
			while j >= 0:
				if count[j] > 0:
					for k in range(0, count[j], 1):
						hist[i][col_no] = j
						col_no += 1
				j -= 1
		max_area = 0
		for i in range(0, R, 1):
			for j in range(0, C, 1):
				curr_area = (j + 1) * hist[i][j]
				if curr_area > max_area:
					max_area = curr_area
		return max_area


class Solution:

	def maxArea(self, A, r, c):
		(m, n) = (len(A), len(A[0]))
		for i in range(m):
			for j in range(n):
				if A[i][j] == 0:
					continue
				A[i][j] += A[i - 1][j] if i > 0 else 0
		for row in A:
			row.sort(reverse=True)
		max_area = 0
		for row in A:
			for (j, val) in enumerate(row):
				max_area = max(max_area, val * (j + 1))
		return max_area


class Solution:

	def maxArea(self, mat, r, c):
		count = [[0 for j in range(c)] for i in range(r)]
		for i in range(r):
			for j in range(c):
				if i == 0:
					count[i][j] = mat[i][j]
				elif mat[i][j] == 1 and mat[i - 1][j] == 1:
					count[i][j] = count[i - 1][j] + 1
				elif mat[i][j] == 1 and mat[i - 1][j] == 0:
					count[i][j] = 1
		for i in range(r):
			count[i].sort(reverse=True)
		max_area = float('-inf')
		for i in range(r):
			for j in range(c):
				if max_area < (j + 1) * count[i][j]:
					max_area = (j + 1) * count[i][j]
		return max_area


class Solution:

	def maxArea(self, mat, r, c):
		for i in range(1, len(mat)):
			for j in range(0, len(mat[0])):
				if mat[i][j] != 0:
					mat[i][j] = 1 + mat[i - 1][j]
		ans = 0
		for i in mat:
			i.sort()
			for j in range(len(i)):
				ans = max(ans, i[j] * (len(i) - j))
		return ans


class Solution:

	def maxArea(self, x, r, c):
		for i in range(r - 2, -1, -1):
			for j in range(c):
				if x[i][j]:
					x[i][j] += x[i + 1][j]
		ans = 0
		for i in range(r):
			x[i].sort()
			for j in range(c):
				ans = max(ans, (c - j) * x[i][j])
		return ans


class Solution:

	def maxArea(self, mat, r, c):
		d = [[0] * (c + 1) for i in range(r + 1)]
		for i in range(r + 1):
			for j in range(c + 1):
				if i == 0 or j == 0:
					continue
				elif mat[i - 1][j - 1] == 1:
					d[i][j] = d[i - 1][j] + 1
		for i in d:
			i.sort(reverse=True)
		area = 0
		for i in range(r + 1):
			for j in range(c + 1):
				cur = (j + 1) * d[i][j]
				area = max(area, cur)
		return area
		print(d)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(r, c) = list(map(int, input().strip().split()))
		inputLine = list(map(int, input().strip().split()))
		mat = [[False for j in range(c)] for i in range(r)]
		k = 0
		for i in range(r):
			for j in range(c):
				mat[i][j] = inputLine[k]
				k += 1
		ob = Solution()
		ans = ob.maxArea(mat, r, c)
		print(ans)
		tc -= 1


class Solution:

	def maxArea(self, mat, r, c):
		(R, C) = (r, c)
		hist = [[0 for i in range(C + 1)] for i in range(R + 1)]
		for i in range(0, C, 1):
			hist[0][i] = mat[0][i]
			for j in range(1, R, 1):
				if mat[j][i] == 0:
					hist[j][i] = 0
				else:
					hist[j][i] = hist[j - 1][i] + 1
		for i in range(0, R, 1):
			hist[i].sort(reverse=True)
		max_area = 0
		for i in range(0, R, 1):
			for j in range(0, C, 1):
				curr_area = (j + 1) * hist[i][j]
				max_area = max(max_area, curr_area)
		return max_area


class Solution:

	def maxArea(self, mat, r, c):
		dp = [[0 for i in range(r + 1)] for j in range(r + 1)]
		for i in range(c):
			ct = 0
			for j in range(r - 1, -1, -1):
				if mat[j][i] == 1:
					ct += 1
				else:
					ct = 0
				dp[j][ct] += 1
		maxv = 0
		for i in range(r):
			mi = 0
			for j in range(r, -1, -1):
				mi += dp[i][j]
				maxv = max(maxv, mi * j)
		return maxv


class Solution:

	def maxArea(self, mat, r, c):
		for i in range(1, r):
			for j in range(c):
				if mat[i - 1][j] > 0 and mat[i][j] > 0:
					mat[i][j] += mat[i - 1][j]
		for i in range(r):
			mat[i] = sorted(mat[i])[::-1]
		mx = 0
		for i in range(r):
			for j in range(c):
				mx = max(mx, mat[i][j] * (j + 1))
		return mx