Given a binary matrix M of size n X m. Find the maximum area of a rectangle formed only of 1s in the given matrix. 
Example 1:
Input:
n = 4, m = 4
M[][] = {{0 1 1 0},
         {1 1 1 1},
         {1 1 1 1},
         {1 1 0 0}}
Output: 8
Explanation: For the above test case the
matrix will look like
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
the max size rectangle is 
1 1 1 1
1 1 1 1
and area is 4 *2 = 8.
Your Task: 
Your task is to complete the function maxArea which returns the maximum size rectangle area in a binary-sub-matrix with all 1’s. The function takes 3 arguments the first argument is the Matrix M[ ] [ ] and the next two are two integers n and m which denotes the size of the matrix M. 
Expected Time Complexity : O(n*m)
Expected Auixiliary Space : O(m)
Constraints:
1<=n,m<=1000
0<=M[][]<=1
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3


class Solution:
    def maxArea(self,M, n, m):
        # code here

Solutions:
class Solution:

	def maxrect(self, arr, n):
		ps = [1]
		for i in range(1, n):
			k = i - 1
			count = 1
			while k >= 0 and arr[i] <= arr[k] and (arr[i] != 0):
				count += ps[k]
				k -= ps[k]
			ps.append(count)
		ns = [1] * n
		for i in range(n - 2, -1, -1):
			k = i + 1
			count = 1
			while k < n and arr[i] <= arr[k] and (arr[i] != 0):
				count += ns[k]
				k += ns[k]
			ns[i] = count
		maxi = 0
		for i in range(n):
			maxi = max(maxi, (abs(ns[i] + ps[i]) - 1) * arr[i])
		return maxi

	def maxArea(self, M, n, m):
		arr = [0] * m
		maxi = 0
		for i in range(n):
			for j in range(m):
				if M[i][j] == 1:
					arr[j] += 1
				else:
					arr[j] = 0
			maxi = max(maxi, self.maxrect(arr, m))
		return maxi


class Solution:

	def maxArea(self, matrix, rows, cols):
		shiftRow = [0] * cols
		sol = 0
		for row in matrix:
			for (i, ele) in enumerate(row):
				if ele == 1:
					shiftRow[i] += 1
				else:
					shiftRow[i] = 0
			st = []
			for i in range(cols + 1):
				while len(st) > 0 and (i == cols or shiftRow[st[-1]] >= shiftRow[i]):
					height = shiftRow[st[-1]]
					st.pop()
					width = i
					if len(st) > 0:
						width = i - st[-1] - 1
					sol = max(height * width, sol)
				st.append(i)
		return sol


class Solution:

	def maxArea(self, M, n, m):
		hist = [0] * m
		max_area = 0
		for i in range(n):
			for j in range(m):
				if M[i][j] == 0:
					hist[j] = 0
				else:
					hist[j] += 1
			stack = []
			j = 0
			while j < m:
				if not stack or hist[stack[-1]] <= hist[j]:
					stack.append(j)
					j += 1
				else:
					top = stack.pop()
					area = hist[top] * (j - stack[-1] - 1 if stack else j)
					max_area = max(max_area, area)
			while stack:
				top = stack.pop()
				area = hist[top] * (j - stack[-1] - 1 if stack else j)
				max_area = max(max_area, area)
		return max_area


def getarea(height):
	n = len(height)
	(nxt, prev) = ([n] * n, [-1] * n)
	stack = []
	for i in range(n):
		while stack and height[stack[-1]] >= height[i]:
			nxt[stack[-1]] = i
			stack.pop()
		prev[i] = stack[-1] if stack else -1
		stack.append(i)
	area = -1
	for i in range(n):
		length = height[i]
		width = nxt[i] - prev[i] - 1
		newarea = length * width
		area = max(area, newarea)
	return area

class Solution:

	def maxArea(self, M, n, m):
		height = [0] * m
		area = -1
		for i in range(n):
			for j in range(m):
				if M[i][j] == 0:
					height[j] = 0
				else:
					height[j] += M[i][j]
			newarea = getarea(height)
			area = max(area, newarea)
		return area


class Solution:

	def maxArea(self, M, n, m):
		ans = 0
		for j in range(n):
			if j == 0:
				histogram = M[0]
			else:
				for k in range(m):
					if M[j][k] == 0:
						histogram[k] = 0
					else:
						histogram[k] += 1
			(s, res, n, curr) = ([], 0, m, 0)
			for i in range(n):
				while len(s) != 0 and histogram[s[-1]] >= histogram[i]:
					temp = s.pop()
					if len(s) == 0:
						curr = histogram[temp] * i
					else:
						curr = histogram[temp] * (i - s[-1] - 1)
					res = max(res, curr)
				s.append(i)
			while len(s) != 0:
				temp = s.pop()
				if len(s) == 0:
					curr = histogram[temp] * n
				else:
					curr = histogram[temp] * (n - s[-1] - 1)
				res = max(res, curr)
			ans = max(ans, res)
		return ans


class Solution:

	def largestRectangleArea(self, row):
		result = []
		top_val = 0
		max_area = 0
		area = 0
		i = 0
		while i < len(row):
			if len(result) == 0 or row[result[-1]] <= row[i]:
				result.append(i)
				i += 1
			else:
				top_val = row[result.pop()]
				area = top_val * i
				if len(result):
					area = top_val * (i - result[-1] - 1)
				max_area = max(area, max_area)
		while len(result):
			top_val = row[result.pop()]
			area = top_val * i
			if len(result):
				area = top_val * (i - result[-1] - 1)
			max_area = max(area, max_area)
		return max_area

	def maxArea(self, M, n, m):
		area = self.largestRectangleArea(M[0])
		for i in range(1, n):
			for j in range(m):
				if M[i][j] != 0:
					M[i][j] = M[i][j] + M[i - 1][j]
				else:
					M[i][j] = 0
			area = max(area, self.largestRectangleArea(M[i]))
		return area


class Solution:

	def maxArea(self, M, n, m):

		def getMaxArea(histogram):
			stack = []
			res = 0
			n = len(histogram)
			for i in range(n):
				while stack != [] and histogram[stack[-1]] >= histogram[i]:
					top = stack[-1]
					stack.pop()
					if stack != []:
						curr_width = i - stack[-1] - 1
					else:
						curr_width = i
					res = max(res, curr_width * histogram[top])
				stack.append(i)
			while stack != []:
				top = stack[-1]
				stack.pop()
				if stack != []:
					curr_width = n - stack[-1] - 1
				else:
					curr_width = n
				res = max(res, curr_width * histogram[top])
			return res
		res = getMaxArea(M[0])
		for i in range(1, len(M)):
			for j in range(len(M[i])):
				if M[i][j]:
					M[i][j] += M[i - 1][j]
			res = max(res, getMaxArea(M[i]))
		return res


class Solution:

	def calMaxArea(self, heights):
		n = len(heights)
		maxi = 0
		stack = []
		for (i, h) in enumerate(heights):
			start = i
			while stack and stack[-1][1] > h:
				(ind, height) = stack.pop()
				maxi = max(maxi, height * (i - ind))
				start = ind
			stack.append((start, h))
		for (i, h) in stack:
			maxi = max(maxi, h * (n - i))
		return maxi

	def maxArea(self, M, n, m):
		hist = M[0]
		res = self.calMaxArea(hist)
		for i in range(1, n):
			for j in range(m):
				if M[i][j] == 0:
					hist[j] = 0
				else:
					hist[j] += 1
			res = max(res, self.calMaxArea(hist))
		return res


class Solution:

	def maxArea(self, M, n, m):

		def maxhistrogram(height):
			st = []
			res = 0
			for i in range(len(height)):
				while st and height[st[-1]] >= height[i]:
					tp = st[-1]
					st.pop()
					curr_width = i - st[-1] - 1 if st else i
					res = max(res, curr_width * height[tp])
				st.append(i)
			while st:
				tp = st[-1]
				st.pop()
				curr_width = len(height) - st[-1] - 1 if st else len(height)
				res = max(res, curr_width * height[tp])
			return res
		res = maxhistrogram(M[0])
		for i in range(1, len(M)):
			for j in range(len(M[i])):
				if M[i][j]:
					M[i][j] += M[i - 1][j]
			res = max(res, maxhistrogram(M[i]))
		return res


class Solution:

	def maxHist(self, row, C):
		result = list()
		top_val = 0
		max_area = 0
		area = 0
		i = 0
		while i < C:
			if len(result) == 0 or row[result[-1]] <= row[i]:
				result.append(i)
				i += 1
			else:
				top_val = row[result[-1]]
				result.pop()
				area = top_val * i
				if len(result):
					area = top_val * (i - result[-1] - 1)
				max_area = max(area, max_area)
		while len(result):
			top_val = row[result[-1]]
			result.pop()
			area = top_val * i
			if len(result):
				area = top_val * (i - result[-1] - 1)
			max_area = max(area, max_area)
		return max_area

	def maxArea(self, A, R, C):
		result = self.maxHist(A[0], C)
		for i in range(1, R):
			for j in range(C):
				if A[i][j]:
					A[i][j] += A[i - 1][j]
			result = max(result, self.maxHist(A[i], C))
		return result


class Solution:

	def max_hist(self, row):
		max_area = 0
		ind = 0
		n = len(row)
		stack = []
		while ind < n:
			if len(stack) == 0 or row[ind] >= row[stack[-1]]:
				stack.append(ind)
				ind += 1
			else:
				top_val = row[stack.pop()]
				area = top_val * ind
				if len(stack) > 0:
					area = top_val * (ind - stack[-1] - 1)
				max_area = max(max_area, area)
		while len(stack) != 0:
			top_val = row[stack.pop()]
			area = top_val * ind
			if len(stack) > 0:
				area = top_val * (ind - stack[-1] - 1)
			max_area = max(area, max_area)
		return max_area

	def maxArea(self, M, n, m):
		max_area = self.max_hist(M[0])
		for i in range(1, n):
			for j in range(m):
				if M[i][j] == 1:
					M[i][j] += M[i - 1][j]
			curr_area = self.max_hist(M[i])
			max_area = max(max_area, curr_area)
		return max_area


from collections import deque

def MA(a, n):
	s = deque()
	res = max(a)
	for i in range(n):
		while s and a[i] <= a[s[-1]]:
			tp = s.pop()
			if s:
				curr = i - s[-1] - 1
			else:
				curr = i
			res = max(res, a[tp] * curr)
		s.append(i)
	while s:
		tp = s.pop()
		if s:
			curr = n - s[-1] - 1
		else:
			curr = n
		res = max(res, a[tp] * curr)
	return res

class Solution:

	def maxArea(self, M, n, m):
		result = MA(M[0], m)
		for i in range(1, n):
			for j in range(m):
				if M[i][j]:
					M[i][j] += M[i - 1][j]
			result = max(result, MA(M[i], m))
		return result


class Solution:

	def maxArea(self, mat, n, m):

		def maxHist(row):
			result = []
			top_val = 0
			max_area = 0
			area = 0
			i = 0
			while i < len(row):
				if len(result) == 0 or row[result[-1]] <= row[i]:
					result.append(i)
					i += 1
				else:
					top_val = row[result.pop()]
					area = top_val * i
					if len(result):
						area = top_val * (i - result[-1] - 1)
					max_area = max(area, max_area)
			while len(result):
				top_val = row[result.pop()]
				area = top_val * i
				if len(result):
					area = top_val * (i - result[-1] - 1)
				max_area = max(area, max_area)
			return max_area

		def maxRectangle(A):
			result = maxHist(A[0])
			for i in range(1, len(A)):
				for j in range(len(A[i])):
					if A[i][j]:
						A[i][j] += A[i - 1][j]
				result = max(result, maxHist(A[i]))
			return result
		return maxRectangle(mat)


class Solution:

	def maxArea(self, M, n, m):
		heights = [0] * m
		max_area = 0
		for i in range(n):
			for j in range(m):
				if M[i][j] == 0:
					heights[j] = 0
				else:
					heights[j] += 1
			area = self.largestRectangleArea(heights)
			max_area = max(max_area, area)
		return max_area

	def largestRectangleArea(self, heights):
		stack = []
		max_area = 0
		for i in range(len(heights)):
			while stack and heights[i] < heights[stack[-1]]:
				height = heights[stack.pop()]
				width = i if not stack else i - stack[-1] - 1
				area = height * width
				max_area = max(max_area, area)
			stack.append(i)
		while stack:
			height = heights[stack.pop()]
			width = len(heights) if not stack else len(heights) - stack[-1] - 1
			area = height * width
			max_area = max(max_area, area)
		return max_area


class Solution:

	def maxArea(self, M, n, m):
		if not n or not m:
			return 0
		dp = [[0] * m for _ in range(n)]
		for i in range(n):
			acc = 0
			for j in range(m):
				if M[i][j] == 1:
					acc += 1
				else:
					acc = 0
				dp[i][j] = acc
		res = 0
		for i in reversed(range(n)):
			for j in reversed(range(m)):
				(bSide, rSide) = (dp[i][j], 0)
				k = i
				while k > -1 and dp[k][j]:
					bSide = min(bSide, dp[k][j])
					rSide += 1
					res = max(res, bSide * rSide)
					k -= 1
		return res


class Solution:

	def maxArea(self, matrix, n, m):
		m = len(matrix)
		n = len(matrix[0])
		dp = [0 for _ in range(n)]

		def max_histogram(heights):
			stk = []
			max_area = 0
			for (i, el) in enumerate(heights + [0]):
				while stk and heights[stk[-1]] > el:
					H = heights[stk.pop()]
					if not stk:
						W = i
					else:
						W = i - stk[-1] - 1
					max_area = max(max_area, int(H * W))
				stk.append(i)
			return max_area
		res = 0
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 0:
					dp[j] = 0
				else:
					dp[j] = dp[j] + matrix[i][j]
			res = max(res, max_histogram(dp))
		return res


class Solution:

	def mah(self, a, n, x=0):
		freq = [0] * n
		stack = []
		for i in range(n - 1, -1, -1):
			while stack != [] and a[stack[-1]] >= a[i]:
				stack.pop()
			if stack == []:
				freq[i] = n
				stack.append(i)
				continue
			freq[i] = stack[-1]
			stack.append(i)
		stack = []
		for i in range(n):
			while stack != [] and a[stack[-1]] >= a[i]:
				stack.pop()
			if stack == []:
				freq[i] = freq[i] * a[i]
				stack.append(i)
				continue
			freq[i] = (freq[i] - stack[-1] - 1) * a[i]
			stack.append(i)
		return max(freq)

	def maxArea(self, M, n, m):
		for i in range(n):
			if i == 0:
				res = self.mah(M[i], m)
				ans = M[i]
				continue
			for j in range(m):
				if M[i][j] == 0:
					ans[j] = 0
					continue
				ans[j] += M[i][j]
			res = max(res, self.mah(ans, m))
		return res


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		height = []
		maxArea = 0
		for (i, h) in enumerate(histogram):
			start = i
			while height and height[-1][1] > h:
				(index, hei) = height.pop()
				maxArea = max(maxArea, hei * (i - index))
				start = index
			height.append((start, h))
		for (i, h) in height:
			maxArea = max(maxArea, h * (n - i))
		return maxArea

	def maxArea(self, M, n, m):
		maxi = 0
		stack = []
		for i in range(n):
			l = []
			for j in range(m):
				if i == 0:
					l.append(M[i][j])
				elif M[i][j] == 0:
					l.append(0)
				else:
					l.append(stack[i - 1][j] + M[i][j])
			maxi = max(maxi, self.getMaxArea(l))
			stack.append(l)
		return maxi


class Solution:

	def maxArea(self, matrix, n, m):
		for row in range(len(matrix)):
			matrix[row].append('0')
		height = [0] * len(matrix[0])
		max_rectangle = 0
		for row in matrix:
			stack = [-1]
			for (col, val) in enumerate(row):
				height[col] = (height[col] + 1) * int(val)
				while height[stack[-1]] > height[col]:
					prev_col = stack.pop()
					left = prev_col - stack[-1] - 1
					right = col - prev_col
					width = left + right
					area = width * height[prev_col]
					max_rectangle = max(max_rectangle, area)
				stack.append(col)
		return max_rectangle


class Solution:

	def largestRect(self, a):
		n = len(a)
		stack = []
		maxArea = 0
		i = 0
		while i < n:
			if not stack or a[stack[-1]] < a[i]:
				stack.append(i)
				i += 1
			else:
				t = a[stack.pop()]
				area = t * (i - stack[-1] - 1) if stack else t * i
				maxArea = max(area, maxArea)
		while stack:
			t = a[stack.pop()]
			area = t * (i - stack[-1] - 1) if stack else t * i
			maxArea = max(area, maxArea)
		return maxArea

	def maxArea(self, a, n, m):
		maxArea = self.largestRect(a[0])
		for i in range(1, n):
			for j in range(m):
				if a[i][j] == 1:
					a[i][j] += a[i - 1][j]
			area = self.largestRect(a[i])
			maxArea = max(area, maxArea)
		return maxArea


class Solution:

	def maxArea(self, M, R, C):

		def maxHis(arr):
			n = len(arr)
			stack = []
			nsri = [n for i in range(n)]
			for i in range(n):
				while stack and arr[stack[-1]] > arr[i]:
					nsri[stack.pop()] = i
				stack.append(i)
			stack = []
			nsli = [-1 for i in range(n)]
			for i in range(n - 1, -1, -1):
				while stack and arr[stack[-1]] > arr[i]:
					nsli[stack.pop()] = i
				stack.append(i)
			width = []
			for i in range(n):
				width.append((nsri[i] - nsli[i] - 1) * arr[i])
			return max(width)
		ans = float('-inf')
		l = [0] * C
		for i in range(R):
			for k in range(C):
				if M[i][k] == 0:
					l[k] = 0
				else:
					l[k] += 1
			ans = max(ans, maxHis(l.copy()))
		return ans


class Solution:

	def maxi(self, row):
		res = []
		(top, area, maxArea) = (0, 0, 0)
		i = 0
		while i < len(row):
			if len(res) == 0 or row[res[-1]] <= row[i]:
				res.append(i)
				i += 1
			else:
				top = row[res.pop()]
				area = top * i
				if len(res):
					area = top * (i - res[-1] - 1)
				maxArea = max(area, maxArea)
		while len(res):
			top = row[res.pop()]
			area = top * i
			if len(res):
				area = top * (i - res[-1] - 1)
			maxArea = max(area, maxArea)
		return maxArea

	def maxArea(self, M, n, m):
		res = self.maxi(M[0])
		for i in range(1, n):
			for j in range(m):
				if M[i][j]:
					M[i][j] += M[i - 1][j]
			res = max(res, self.maxi(M[i]))
		return res


class Solution:

	def maxArea(self, M, n, m):
		height = [0] * m
		max_area = 0
		for i in range(n):
			for j in range(m):
				if M[i][j] == 0:
					height[j] = 0
				else:
					height[j] += 1
			stack = []
			for j in range(m):
				while stack and height[stack[-1]] > height[j]:
					top = stack.pop()
					area = height[top] * (j - stack[-1] - 1 if stack else j)
					max_area = max(max_area, area)
				stack.append(j)
			while stack:
				top = stack.pop()
				area = height[top] * (m - stack[-1] - 1 if stack else m)
				max_area = max(max_area, area)
		return max_area


from collections import deque

class Solution:

	def maxHist(self, row):
		result = []
		top_val = 0
		max_area = 0
		area = 0
		i = 0
		while i < len(row):
			if len(result) == 0 or row[result[-1]] <= row[i]:
				result.append(i)
				i += 1
			else:
				top_val = row[result.pop()]
				area = top_val * i
				if len(result):
					area = top_val * (i - result[-1] - 1)
				max_area = max(area, max_area)
		while len(result):
			top_val = row[result.pop()]
			area = top_val * i
			if len(result):
				area = top_val * (i - result[-1] - 1)
			max_area = max(area, max_area)
		return max_area

	def maxArea(self, M, n, m):
		result = self.maxHist(A[0])
		for i in range(1, len(A)):
			for j in range(len(A[i])):
				if A[i][j]:
					A[i][j] += A[i - 1][j]
			result = max(result, self.maxHist(A[i]))
		return result


class Solution:

	def maxArea(self, M, n, m):

		def largestRectangleArea(heights):
			stack = []
			max_area = 0
			i = 0
			while i < len(heights):
				if not stack or heights[i] >= heights[stack[-1]]:
					stack.append(i)
					i += 1
				else:
					top = stack.pop()
					area = heights[top] * (i - stack[-1] - 1 if stack else i)
					max_area = max(max_area, area)
			while stack:
				top = stack.pop()
				area = heights[top] * (i - stack[-1] - 1 if stack else i)
				max_area = max(max_area, area)
			return max_area

		def maxRectangleArea(M):
			n = len(M)
			m = len(M[0])
			histogram = [0] * m
			max_area = 0
			for i in range(n):
				for j in range(m):
					if M[i][j] == 0:
						histogram[j] = 0
					else:
						histogram[j] += 1
				area = largestRectangleArea(histogram)
				max_area = max(max_area, area)
			return max_area
		return maxRectangleArea(M)


class Solution:

	def maxArea(self, M, n, m):
		arr = M[0]
		res = -1
		res = max(res, getmaxarea(arr))
		for i in range(1, n):
			for j in range(m):
				if M[i][j] == 0:
					arr[j] = 0
				else:
					arr[j] = arr[j] + M[i][j]
			res = max(res, getmaxarea(arr))
		return res

def getmaxarea(h):
	h.append(0)
	stack = []
	area = 0
	i = 0
	while i < len(h):
		if not stack or h[stack[-1]] < h[i]:
			stack.append(i)
			i += 1
		else:
			top = stack.pop()
			area = max(area, h[top] * (i - stack[-1] - 1 if stack else i))
	return area