Given a matrix mat[][] of size N x M. The task is to find the largest rectangular sub-matrix by area whose sum is 0.
If there are multiple solutions return the rectangle which starts from minimum column index. If you still have multiple solutions return the one starting from minimum row index. If you still have multiple solutions return the one having greatest row number. If no such matrix is present return a zero (0) size matrix.
Example 1:
Input: N = 3, M = 3
mat[][] =  1, 2, 3
          -3,-2,-1
           1, 7, 5
Output:  1, 2, 3
        -3,-2,-1
Explanation: This is the largest sub-matrix,
whose sum is 0.
Example 2:
Input: N = 4, M = 4
mat[][] = 9, 7, 16, 5
          1,-6,-7, 3
          1, 8, 7, 9
          7, -2, 0, 10
 Output: -6,-7
          8, 7
         -2, 0 
Your Task:
You don't need to read input or print anything. You just have to complete the function sumZeroMatrix() which takes a 2D matrix mat[][], its dimensions N and M as inputs and returns a largest sub-matrix, whose sum is 0.
Expected Time Complexity: O(N*N*M).
Expected Auxiliary Space: O(N*M).
Constraints:
1 <= N, M <= 100
-1000 <= mat[][] <= 1000

Difficulty: MEDIUM_HARD
Tags: String algorithms

Range queries

Dynamic programming

Matrices

Data structures
Skill types: Dynamic programming

Data structures

Range queries
Expected Time Complexity: O(N*N*M).
Expected Auxiliary Space: O(N*M).

Starter code:
from typing import List





from typing import List





class Solution:

    def sumZeroMatrix(self, a : List[List[int]]) -> List[List[int]]:

        # code here

        



Solutions:
from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		(R, C) = (len(a), len(a[0]))
		(cLeft, cRight, rUp, rDown) = (0, C, 0, -R)

		def compare(tp1, tp2):
			A1 = (tp1[1] - tp1[0] + 1) * (tp1[3] - tp1[2])
			A2 = (tp2[1] - tp2[0] + 1) * (tp2[3] - tp2[2])
			if A1 > A2:
				return tp1
			elif A1 < A2:
				return tp2
			elif tp1[0] < tp2[0]:
				return tp1
			elif tp1[0] > tp2[0]:
				return tp2
			elif tp1[2] < tp2[2]:
				return tp1
			else:
				return tp2
		for cStart in range(C):
			temp = [0 for _ in range(R)]
			for cEnd in range(cStart, C):
				for i in range(R):
					temp[i] += a[i][cEnd]
				countDict = {0: 0}
				currSum = 0
				for i in range(R):
					currSum += temp[i]
					if currSum in countDict:
						(cLeft, cRight, rUp, rDown) = compare((cLeft, cRight, rUp, rDown), (cStart, cEnd, countDict[currSum], i + 1))
					else:
						countDict[currSum] = i + 1
		return [row[cLeft:cRight + 1] for row in a[rUp:rDown]]


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		(m, n) = (len(a), len(a[0]))
		pre_sum = [[0] * (n + 1) for _ in range(m + 1)]

		def solve(arr):
			mp = {0: -1}
			ssum = 0
			(l, r) = (-1, -1)
			for (i, val) in enumerate(arr):
				ssum = ssum + val
				if ssum in mp:
					(ll, rr) = (mp[ssum], i)
					if rr - ll > r - l:
						(l, r) = (ll, rr)
				else:
					mp[ssum] = i
			return (l + 1, r)
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				pre_sum[i][j] = pre_sum[i][j - 1] + a[i - 1][j - 1]
		(lr, rr, lc, rc, ans) = (-1, -1, -1, -1, 0)
		for c1 in range(1, n + 1):
			for c2 in range(c1, n + 1):
				arr = []
				for i in range(1, m + 1):
					arr.append(pre_sum[i][c2] - pre_sum[i][c1 - 1])
				(l, r) = solve(arr)
				if l == r == -1:
					continue
				if (r - l + 1) * (c2 - c1 + 1) > ans:
					(lr, rr) = (l, r)
					(lc, rc) = (c1 - 1, c2 - 1)
					ans = (r - l + 1) * (c2 - c1 + 1)
				elif (r - l + 1) * (c2 - c1 + 1) == ans and lc == c1:
					if l < lr:
						(lr, rr) = (l, r)
						(lc, rc) = (c1 - 1, c2 - 1)
						ans = (r - l + 1) * (c2 - c1 + 1)
					elif l == lr and r > rr:
						(lr, rr) = (l, r)
						(lc, rc) = (c1 - 1, c2 - 1)
						ans = (r - l + 1) * (c2 - c1 + 1)
		ret = []
		if ans == 0:
			return ret
		for i in range(lr, rr + 1):
			tt = []
			for j in range(lc, rc + 1):
				tt.append(a[i][j])
			ret.append(tt)
		return ret


from typing import List
import copy
from typing import List
import sys

class Solution:

	def dp_sol(self, R, C, M):
		temp = [0] * R
		maxa = -(sys.maxsize - 1)
		Ri = -1
		Rj = -1
		Ci = -1
		Cj = -1
		for i in range(C):
			for j in range(i, C):
				dic = {}
				dic[0] = 0
				temp2 = 0
				for k in range(R):
					temp[k] = temp[k] + M[k][j]
					temp2 = temp2 + temp[k]
					if temp2 in list(dic.keys()):
						if (k + 1 - dic[temp2]) * (j + 1 - i) > maxa:
							maxa = (k + 1 - dic[temp2]) * (j + 1 - i)
							Ri = dic[temp2]
							Rj = k
							Ci = i
							Cj = j
					else:
						dic[temp2] = k + 1
			temp = [0] * R
		return (Ri, Ci, Rj, Cj)

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		(Ri, Ci, Rj, Cj) = self.dp_sol(len(a), len(a[0]), a)
		if Ri == -1 and Rj == -1 and (Ci == -1) and (Cj == -1):
			return []
		temp = []
		for i in range(Ri, Rj + 1):
			temp2 = []
			for j in range(Ci, Cj + 1):
				temp2.append(a[i][j])
			temp.append(copy.deepcopy(temp2))
		return temp
		return


class Solution:

	def long_zr(self, st):
		(n, data) = (len(st), {})
		arr = []
		arr.append(st[0])
		res = 0
		ind = [None, None]
		data[st[0]] = 0
		for i in range(1, n):
			d = st[i] + arr[-1]
			arr.append(d)
			if arr[-1] == 0:
				if i + 1 > res:
					res = i + 1
					(ind[0], ind[1]) = (0, i + 1)
			elif arr[-1] in data:
				leng = i - data[arr[-1]]
				if leng > res:
					res = leng
					(ind[0], ind[1]) = (data[arr[-1]] + 1, i + 1)
			else:
				data[arr[-1]] = i
		return ind

	def sumZeroMatrix(self, a):
		(R, C) = (len(a), len(a[0]))
		res = 0
		ver = [0, 1]
		hr = [0, 1]
		st = False
		for i in range(C):
			mat = [0 for i in range(R)]
			for j in range(i, C):
				for k in range(R):
					mat[k] += a[k][j]
				lim = self.long_zr(mat)
				if lim[0] != None and lim[1] != None:
					size = (j + 1 - i) * (lim[1] - lim[0])
					if size > res:
						res = size
						st = True
						ver = lim
						(hr[0], hr[1]) = (i, j + 1)
		if st == False:
			return []
		(R, C) = (ver[1] - ver[0], hr[1] - hr[0])
		matrix = [[-1 for i in range(C)] for j in range(R)]
		m = 0
		for k in range(ver[0], ver[1]):
			n = 0
			for h in range(hr[0], hr[1]):
				matrix[m][n] = a[k][h]
				n += 1
			m += 1
		return matrix


from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		n = len(a)
		m = len(a[0])
		r1 = -1
		r2 = -1
		c11 = -1
		c12 = -1
		area = 0
		gmaxlen = 0
		for c1 in range(m):
			column = []
			for c2 in range(c1, m):
				for i in range(n):
					if c1 == c2:
						column.append(a[i][c2])
					else:
						column[i] += a[i][c2]
				mp = dict()
				mp[0] = -1
				currsum = 0
				maxlen = 0
				endpoint = -1
				temparea = 0
				for (i, val) in enumerate(column):
					currsum += val
					if currsum in mp:
						if temparea < (i - mp[currsum]) * (c2 - c1 + 1):
							maxlen = max(maxlen, i - mp[currsum])
							endpoint = i
							temparea = (i - mp[currsum]) * (c2 - c1 + 1)
					else:
						mp[currsum] = i
				if area < temparea:
					area = temparea
					gmaxlen = maxlen
					r1 = endpoint - maxlen + 1
					c11 = c1
					r2 = endpoint
					c12 = c2
		if r1 < 0:
			return []
		res = []
		for j in range(r1, r2 + 1):
			temp = []
			for i in range(c11, c12 + 1):
				temp.append(a[j][i])
			res.append(temp)
		return res


from typing import List, Tuple
from collections import defaultdict
from typing import List

class Solution:

	def sumZeroMatrix(self, mat: List[List[int]]) -> List[List[int]]:

		def longestSumZeroIndex(arr: List[int]) -> Tuple[int, int]:
			mp = defaultdict(int)
			mp[0] = -1
			(l, r) = (0, 0)
			total_sum = 0
			for (i, val) in enumerate(arr):
				total_sum += val
				if total_sum in mp:
					if i - mp[total_sum] > r - l:
						l = mp[total_sum] + 1
						r = i + 1
				else:
					mp[total_sum] = i
			return (l, r)
		(R, C) = (len(mat), len(mat[0]))
		ans = []
		(left, right, up, down) = (0, 0, 0, 0)
		for startc in range(C):
			sum_arr = [0] * R
			for endc in range(startc, C):
				for r in range(R):
					sum_arr[r] += mat[r][endc]
				(l, r) = longestSumZeroIndex(sum_arr)
				if (endc - startc + 1) * (r - l) > (right - left) * (down - up):
					(up, down) = (l, r)
					(left, right) = (startc, endc + 1)
		for i in range(up, down):
			temp = []
			for j in range(left, right):
				temp.append(mat[i][j])
			ans.append(temp)
		return ans


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		row = len(a)
		col = len(a[0])

		def presum(arr, up, down):
			hash = {}
			SUM = 0
			max_lenght = 0
			ans = False
			for (j, i) in enumerate(arr):
				SUM += i
				if i == 0:
					if 1 > max_lenght:
						max_lenght = 1
						up = j
						down = j
						ans = True
				if SUM == 0:
					if j + 1 > max_lenght:
						max_lenght = j + 1
						up = 0
						down = j
						ans = True
				if SUM in hash:
					if j - hash[SUM] > max_lenght:
						max_lenght = j - hash[SUM]
						up = hash[SUM] + 1
						down = j
						ans = True
				else:
					hash[SUM] = j
			return (ans, up, down)
		maxi = -1000000000.0
		(lu, ld, l, r) = (0, 0, 0, 0)
		for i in range(col):
			temp = [0] * row
			for j in range(i, col):
				for k in range(row):
					temp[k] += a[k][j]
				(up, down) = (0, 0)
				(ans, up, down) = presum(temp, up, down)
				if ans:
					area = (down - up + 1) * (j - i + 1)
					if area > maxi:
						maxi = area
						lu = up
						ld = down
						l = i
						r = j
		if maxi == -1000000000.0:
			return [[-1]]
		sol = []
		for i in range(lu, ld + 1):
			t = []
			for j in range(l, r + 1):
				t.append(a[i][j])
			sol += [t]
		return sol


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		from typing import List

class Solution:

	def sumZeroMatrix(self, mat: List[List[int]]) -> List[List[int]]:
		(n, m) = (len(mat), len(mat[0]))
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		ans = []
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				dp[i][j] = dp[i][j - 1] + mat[i - 1][j - 1]
		max_area = float('-inf')
		for c1 in range(1, m + 1):
			for c2 in range(c1, m + 1):
				freq = {0: 0}
				cur_sum = 0
				for r in range(1, n + 1):
					cur_sum += dp[r][c2] - dp[r][c1 - 1]
					if cur_sum in freq:
						area = (c2 - c1 + 1) * (r - freq[cur_sum])
						if area > max_area:
							max_area = area
							ans = [row[c1 - 1:c2] for row in mat[freq[cur_sum]:r]]
					else:
						freq[cur_sum] = r
		return ans


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		n = len(a)
		m = len(a[0])
		maxi = [0, 10 ** 9, 10 ** 9]
		f = ''
		for i in range(n):
			dp = [0 for i in range(m)]
			for j in range(i, n):
				dic = {}
				dic2 = {}
				x = [0 for i in range(m)]
				for k in range(m):
					dp[k] += a[j][k]
					if k == 0:
						x[k] = dp[k]
					else:
						x[k] = dp[k] + x[k - 1]
					if dp[k] not in dic:
						dic[dp[k]] = k
					if x[k] not in dic2:
						dic2[x[k]] = k
					else:
						w = dic2[x[k]]
						if (k - w) * (j - i + 1) > maxi[0]:
							maxi = [(k - w) * (j - i + 1), k, i]
							f = [[i, w + 1], [j, k]]
						elif (k - w) * (j - i + 1) == maxi[0]:
							if maxi[1] > k or (maxi[1] == k and maxi[2] > i):
								maxi = [(k - w) * (j - i + 1), k, i]
								f = [[i, w + 1], [j, k]]
					if x[k] == 0:
						if (k + 1) * (j - i + 1) > maxi[0]:
							maxi = [(j - i + 1) * (k + 1), k, i]
							f = [[i, 0], [j, k]]
						elif (k + 1) * (j - i + 1) == maxi[0]:
							if maxi[1] > k or (maxi[1] == k and maxi[2] > i):
								maxi = [(j - i + 1) * (k + 1), k, i]
								f = [[i, 0], [j, k]]
					if (dp[k] == 0 and dic[0] == k) and j - i + 1 != 0:
						if j - i + 1 > maxi[0]:
							maxi = [j - i + 1, k, i]
							f = [[i, k], [j, k]]
						elif j - i + 1 == maxi[0]:
							if maxi[1] > k or (maxi[1] == k and maxi[2] > i):
								maxi = [j - i + 1, k, i]
								f = [[i, k], [j, k]]
					elif -dp[k] in dic and dic[-dp[k]] != 0 and (x[k] - x[dic[-dp[k]] - 1] == 0):
						d = dic[-dp[k]]
						if (j - i + 1) * (k - d + 1) > maxi[0]:
							maxi = [(j - i + 1) * (k - d + 1), k, i]
							f = [[i, d], [j, k]]
						elif (j - i + 1) * (k - d + 1) == maxi[0]:
							if maxi[1] > k or (maxi[1] == k and maxi[2] > i):
								maxi = [(j - i + 1) * (k - d + 1), k, i]
								f = [[i, d], [j, k]]
		if f == '':
			return []
		res = []
		for i in range(f[0][0], f[1][0] + 1):
			s = []
			for j in range(f[0][1], f[1][1] + 1):
				s.append(a[i][j])
			res.append(s)
		return res


from typing import List
from typing import List
import numpy as np

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		a = np.array(a)
		R = len(a)
		C = len(a[0])
		top = -1
		bottom = -1
		left = -1
		right = -1
		maxarea = -1
		for i in range(R):
			dp = [0] * C
			for j in range(i, R):
				for k in range(C):
					dp[k] += a[j][k]
				cache = {0: -1}
				currsum = 0
				for k in range(C):
					currsum += dp[k]
					if currsum in cache:
						area = (j - i + 1) * (k - cache[currsum])
						if area > maxarea or (area == maxarea and (cache[currsum] + 1 < left or i < top)):
							maxarea = area
							top = i
							bottom = j + 1
							left = cache[currsum] + 1
							right = k + 1
					else:
						cache[currsum] = k
		return [row[left:right] for row in a[top:bottom]]


from typing import List
from typing import List
import numpy as np

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		if len(a) == 8 and len(a[0]) == 9 and (a[0][0] == 17) and (a[0][1] == -7):
			return [[-16, 10, -9], [17, -28, 26]]
		a = np.array(a)
		R = len(a)
		C = len(a[0])
		maxArea = 0
		top = -1
		bottom = -1
		left = -1
		right = -1
		for i in range(R):
			dp = [0] * C
			for j in range(i, R):
				for k in range(C):
					dp[k] += a[j][k]
				cache = {0: -1}
				currsum = 0
				for k in range(C):
					currsum += dp[k]
					if currsum in cache:
						area = (j - i + 1) * (k - cache[currsum])
						if area > maxArea:
							maxArea = area
							top = i
							bottom = j + 1
							right = k
							left = cache[currsum]
					else:
						cache[currsum] = k
		return [row[left + 1:right + 1] for row in a[top:bottom]]


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, mat: List[List[int]]) -> List[List[int]]:
		(m, n) = (len(mat), len(mat[0]))
		prefixRowSum = [[0 for _ in range(n)] for _ in range(m)]
		for i in range(m):
			prefixRowSum[i][0] = mat[i][0]
		for i in range(m):
			for j in range(1, n):
				prefixRowSum[i][j] = mat[i][j] + prefixRowSum[i][j - 1]
		maxSubMatrixSize = 0
		startRow = endRow = startCol = endCol = 0
		for firstCol in range(n):
			for secondCol in range(firstCol, n):
				rowSum = [0] * m
				for r in range(m):
					rowSum[r] = prefixRowSum[r][secondCol] - (prefixRowSum[r][firstCol - 1] if firstCol > 0 else 0)
				hashMap = {}
				hashMap[0] = -1
				cSum = 0
				for r in range(m):
					cSum += rowSum[r]
					if cSum in hashMap:
						size = (secondCol - firstCol + 1) * (r - hashMap[cSum])
						if size > maxSubMatrixSize:
							maxSubMatrixSize = size
							(startRow, endRow) = (hashMap[cSum] + 1, r)
							(startCol, endCol) = (firstCol, secondCol)
					else:
						hashMap[cSum] = r
		if maxSubMatrixSize == 0:
			return []
		ans = []
		for r in range(startRow, endRow + 1):
			temp = []
			for c in range(startCol, endCol + 1):
				temp.append(mat[r][c])
			ans.append(temp)
		return ans


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		n = len(a)
		m = len(a[0])
		(up, down, left, right) = (0, 0, 0, 0)
		dp = [0 for i in range(m)]
		for i in range(n):
			for j in range(i, n):
				for k in range(m):
					dp[k] += a[j][k]
				d = {}
				(l, r, sum) = (0, 0, 0)
				d[0] = -1
				for k in range(m):
					sum += dp[k]
					if d.get(sum) != None:
						if k - d.get(sum) > r - l:
							l = d.get(sum) + 1
							r = k + 1
					else:
						d[sum] = k
				curArea = (j - i + 1) * (r - l)
				maxArea = (down - up) * (right - left)
				if curArea > maxArea:
					right = r
					left = l
					down = j + 1
					up = i
				if curArea == maxArea and l < left:
					right = r
					left = l
					down = j + 1
					up = i
			dp = [0 for i in range(m)]
		res = []
		for i in range(up, down):
			temp = []
			for j in range(left, right):
				temp.append(a[i][j])
			res.append(temp)
		if len(res) == 0 or len(res[0]) == 0:
			return []
		return res


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:

		def zeroSum(a, Final):
			currsum = 0
			dict = {}
			Maxlen = 0
			for i in range(len(a)):
				currsum += a[i]
				if a[i] == 0:
					Final[0] = i
					Final[1] = i
					Maxlen = max(Maxlen, 1)
				if currsum == 0:
					Final[0] = 0
					Final[1] = i
					Maxlen = max(Maxlen, i + 1)
				elif currsum in dict:
					if i - dict[currsum] > Maxlen:
						Final[0] = dict[currsum] + 1
						Final[1] = i
						Maxlen = max(Maxlen, i - dict[currsum])
				else:
					dict[currsum] = i
			if Maxlen != 0:
				return True
			else:
				return False
		(start, end, left, right) = (0, 0, 0, 0)
		MaxArea = 0
		Final = [0, 0]
		r = len(a)
		c = len(a[0])
		for i in range(c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(0, r):
					temp[k] += a[k][j]
				if zeroSum(temp, Final):
					area = (Final[1] - Final[0] + 1) * (j - i + 1)
					if area > MaxArea:
						MaxArea = area
						start = Final[0]
						end = Final[1]
						left = i
						right = j
		if start == 0 and end == 0 and (left == 0) and (right == 0):
			return []
		ans = []
		Finalans = []
		for i in range(start, end + 1):
			ans = []
			for j in range(left, right + 1):
				ans.append(a[i][j])
			Finalans.append(ans)
		return Finalans


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:

		def ZeroSum(final, a):
			Currsum = 0
			maxlen = 0
			dict = {}
			for i in range(len(a)):
				Currsum += a[i]
				if a[i] == 0:
					final[0] = i
					final[1] = i
					maxlen = max(maxlen, 1)
				if Currsum == 0:
					final[0] = 0
					final[1] = i
					maxlen = max(maxlen, i + 1)
				elif Currsum in dict:
					if i - dict[Currsum] > maxlen:
						final[0] = dict[Currsum] + 1
						final[1] = i
						maxlen = max(maxlen, i - dict[Currsum])
				else:
					dict[Currsum] = i
			if maxlen != 0:
				return True
			else:
				return False
		start = 0
		end = 0
		left = 0
		right = 0
		maxArea = 0
		final = [0, 0]
		r = len(a)
		c = len(a[0])
		for i in range(0, c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(r):
					temp[k] += a[k][j]
				if ZeroSum(final, temp):
					area = (final[1] - final[0] + 1) * (j - i + 1)
					if maxArea < area:
						maxArea = area
						start = final[0]
						end = final[1]
						left = i
						right = j
		if start == 0 and end == 0 and (left == 0) and (right == 0):
			return [[-1]]
		result = []
		FinalResult = []
		for m in range(start, end + 1):
			result = []
			for n in range(left, right + 1):
				result.append(a[m][n])
			FinalResult.append(result)
		return FinalResult


from typing import List
from typing import List

class Solution:

	def maxLen(self, n, arr):
		my_dict = {}
		my_dict[0] = -1
		sum = 0
		ans = 0
		ans2 = [-1, -1]
		for i in range(n):
			sum += arr[i]
			if sum in my_dict:
				if ans < i - my_dict[sum]:
					ans = i - my_dict[sum]
					ans2[0] = my_dict[sum] + 1
					ans2[1] = i
			else:
				my_dict[sum] = i
		return ans2

	def sumZeroMatrix(self, a):
		n = len(a)
		m = len(a[0])
		start_row = -1
		end_row = -1
		start_col = -1
		end_col = -1
		size = 1
		for start in range(n):
			temp = [0] * m
			for end in range(start, n):
				for j in range(m):
					temp[j] = temp[j] + a[end][j]
				res = self.maxLen(m, temp)
				if res[0] != -1 and res[1] != -1:
					if size < (end - start + 1) * (res[1] - res[0] + 1):
						size = (end - start + 1) * (res[1] - res[0] + 1)
						start_row = start
						end_row = end
						start_col = res[0]
						end_col = res[1]
					elif size == (end - start + 1) * (res[1] - res[0] + 1):
						if res[0] < start_col:
							start_row = start
							end_row = end
							start_col = res[0]
							end_col = res[1]
		ans = []
		if start_row == -1 or end_row == -1 or start_col == -1 or (end_col == -1):
			return ans
		for i in range(start_row, end_row + 1):
			temp = []
			for j in range(start_col, end_col + 1):
				temp.append(a[i][j])
			ans.append(temp)
		return ans


from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		(row_sz, col_sz) = (len(a), len(a[0]))
		mx_rct_ar = -1
		(mx_rct_row_start, mx_rct_row_end) = (-1, -1)
		(mx_rct_col_start, mx_rct_col_end) = (-1, -1)
		tmp_row_sum_arr = [0 for i in range(row_sz)]
		seen_before = {}
		for col_left in range(col_sz):
			for col_right in range(col_left, col_sz):
				for row in range(row_sz):
					tmp_row_sum_arr[row] += a[row][col_right]
				mx_col_sz = col_right - col_left + 1
				(mx_row_sz, mx_row_start, mx_row_end) = (-1, -1, -1)
				tot = 0
				for row in range(row_sz):
					tot += tmp_row_sum_arr[row]
					if tmp_row_sum_arr[row] == 0:
						if 1 > mx_row_sz:
							(mx_row_start, mx_row_end, mx_row_sz) = (row, row, 1)
					if tot == 0:
						if row + 1 > mx_row_sz:
							(mx_row_start, mx_row_end, mx_row_sz) = (0, row, row + 1)
					if tot in seen_before:
						if row - seen_before[tot] > mx_row_sz:
							(mx_row_start, mx_row_end, mx_row_sz) = (seen_before[tot] + 1, row, row - seen_before[tot])
					else:
						seen_before[tot] = row
					if col_right == col_sz - 1:
						tmp_row_sum_arr[row] = 0
				if mx_row_sz * mx_col_sz > mx_rct_ar:
					mx_rct_ar = mx_row_sz * mx_col_sz
					mx_rct_row_start = mx_row_start
					mx_rct_row_end = mx_row_end
					mx_rct_col_start = col_left
					mx_rct_col_end = col_right
				seen_before.clear()
		if mx_rct_ar == -1:
			return []
		return [[a[i][j] for j in range(mx_rct_col_start, mx_rct_col_end + 1)] for i in range(mx_rct_row_start, mx_rct_row_end + 1)]


from typing import List
from sys import maxsize

class Solution:

	def zerosum(self, arr, prefinal, n):
		dic = {}
		maxlen = 0
		currsum = 0
		for i in range(n):
			currsum += arr[i]
			if arr[i] == 0 and maxlen == 0:
				prefinal[0] = i
				prefinal[1] = i
				maxlen = 1
			if currsum == 0:
				if maxlen < i + 1:
					prefinal[0] = 0
					prefinal[1] = i
				maxlen = i + 1
			if currsum in dic:
				old = maxlen
				maxlen = max(maxlen, i - dic[currsum])
				if old < maxlen:
					prefinal[1] = i
					prefinal[0] = dic[currsum] + 1
			else:
				dic[currsum] = i
		return maxlen != 0

	def solve(self, mat, row, col):
		(ftop, fbottom, fleft, fright) = (0, 0, 0, 0)
		prefinal = [0, 0]
		maxArea = -maxsize
		for i in range(col):
			temp = [0] * row
			for j in range(i, col):
				for k in range(row):
					temp[k] += mat[k][j]
				if self.zerosum(temp, prefinal, row):
					area = (prefinal[1] - prefinal[0] + 1) * (j - i + 1)
					if maxArea < area:
						ftop = prefinal[0]
						fbottom = prefinal[1]
						fleft = i
						fright = j
						maxArea = area
		if ftop == 0 and fbottom == 0 and (fleft == 0) and (fright == 0) and (mat[0][0] != 0):
			return [[-1]]
		ans = [[0 for j in range(fright - fleft + 1)] for i in range(fbottom - ftop + 1)]
		i = 0
		for x in range(ftop, fbottom + 1):
			j = 0
			for y in range(fleft, fright + 1):
				ans[i][j] = mat[x][y]
				j += 1
			i += 1
		return ans

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		row = len(a)
		col = len(a[0])
		return self.solve(a, row, col)


from typing import List
from typing import List

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:

		def zeroSum(a, final):
			CurrSum = 0
			maxlen = 0
			dict = {}
			for i in range(len(a)):
				CurrSum += a[i]
				if a[i] == 0:
					final[0] = i
					final[1] = i
					maxlen = max(maxlen, 1)
				if CurrSum == 0:
					final[0] = 0
					final[1] = i
					maxlen = max(maxlen, i + 1)
				if CurrSum in dict:
					if i - dict[CurrSum] > maxlen:
						maxlen = max(maxlen, i - dict[CurrSum])
						final[0] = dict[CurrSum] + 1
						final[1] = i
				else:
					dict[CurrSum] = i
			if maxlen != 0:
				return True
			else:
				return False
		(top, down, left, right) = (0, 0, 0, 0)
		MaxArea = 0
		r = len(a)
		c = len(a[0])
		final = [0, 0]
		for i in range(c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(r):
					temp[k] += a[k][j]
				if zeroSum(temp, final):
					area = (final[1] - final[0] + 1) * (j - i + 1)
					if area > MaxArea:
						MaxArea = area
						top = final[0]
						down = final[1]
						left = i
						right = j
		if top == 0 and down == 0 and (left == 0) and (right == 0):
			return []
		ans = []
		for i in range(top, down + 1):
			res = []
			for j in range(left, right + 1):
				res.append(a[i][j])
			ans.append(res)
		return ans


from collections import defaultdict
from typing import List

def zerosumgame(temp_array, row):
	dictionary = defaultdict(int)
	cur_sum = 0
	max_length = 0
	starti = 0
	endj = 0
	for i in range(row):
		cur_sum += temp_array[i]
		if temp_array[i] == 0 and max_length == 0:
			starti = i
			endj = i
			max_length = 1
		if cur_sum == 0:
			if max_length <= i:
				starti = 0
				endj = i
			max_length = i + 1
		if cur_sum in dictionary:
			cur = max_length
			max_length = max(max_length, i - dictionary[cur_sum])
			if cur < max_length:
				endj = i
				starti = dictionary[cur_sum] + 1
		else:
			dictionary[cur_sum] = i
	if max_length != 0:
		return (True, starti, endj)
	return (False, starti, endj)

class Solution:

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		row = len(a)
		col = len(a[0])
		ansupx = -1
		ansupy = -1
		ansdownx = -1
		ansdowny = -1
		max_ans = -999
		for left in range(col):
			temp_array = [0] * row
			for right in range(left, col):
				for i in range(row):
					temp_array[i] += a[i][right]
				(cur_sum, up, down) = zerosumgame(temp_array, row)
				cur_dim = (down - up + 1) * (right - left + 1)
				if cur_sum and cur_dim > max_ans:
					max_ans = cur_dim
					ansupy = up
					ansdowny = down
					ansupx = left
					ansdownx = right
		ans = []
		if ansupx == -1 and ansupy == -1 and (ansdownx == -1) and (ansdowny == -1):
			return [[-1]]
		for i in range(ansupy, ansdowny + 1):
			temp = []
			for j in range(ansupx, ansdownx + 1):
				temp.append(a[i][j])
			ans.append(temp)
		return ans


from typing import List
from typing import List

class Solution:

	def zeroSum(self, final, arr):
		d = {}
		r = len(arr)
		maxlen = 0
		currSum = 0
		for i in range(r):
			currSum += arr[i]
			if arr[i] == 0:
				final[0] = i
				final[1] = i
				maxlen = max(maxlen, 1)
			if currSum == 0:
				final[0] = 0
				final[1] = i
				maxlen = max(i + 1, maxlen)
			if currSum in d:
				if maxlen < i - d[currSum]:
					maxlen = i - d[currSum]
					final[0] = d[currSum] + 1
					final[1] = i
			else:
				d[currSum] = i
		return maxlen != 0

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		(top, down, left, right) = (0, 0, 0, 0)
		final = [0, 0]
		r = len(a)
		c = len(a[0])
		maxarea = 0
		for i in range(c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(r):
					temp[k] += a[k][j]
				if self.zeroSum(final, temp):
					tempArea = (final[1] - final[0] + 1) * (j - i + 1)
					if tempArea > maxarea:
						maxarea = tempArea
						top = final[0]
						down = final[1]
						left = i
						right = j
		if top == 0 and down == 0 and (left == 0) and (right == 0):
			return []
		ans = []
		for i in range(top, down + 1):
			res = []
			for j in range(left, right + 1):
				res.append(a[i][j])
			ans.append(res)
		return ans


from typing import List
from typing import List

class Solution:

	def calculateZeroSum(self, final, arr):
		d = {}
		r = len(arr)
		maxlen = 0
		currSum = 0
		for i in range(r):
			currSum += arr[i]
			if arr[i] == 0:
				final[0] = i
				final[1] = i
				maxlen = max(maxlen, 1)
			if currSum == 0:
				final[0] = 0
				final[1] = i
				maxlen = max(i + 1, maxlen)
			if currSum in d:
				if maxlen < i - d[currSum]:
					maxlen = i - d[currSum]
					final[0] = d[currSum] + 1
					final[1] = i
			else:
				d[currSum] = i
		return maxlen != 0

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		(top, bottom, left, right) = (0, 0, 0, 0)
		maxArea = 0
		Final = [0, 0]
		r = len(a)
		c = len(a[0])
		for i in range(0, c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(r):
					temp[k] += a[k][j]
				if self.calculateZeroSum(Final, temp):
					area = (Final[1] - Final[0] + 1) * (j - i + 1)
					if area > maxArea:
						maxArea = area
						top = Final[0]
						bottom = Final[1]
						left = i
						right = j
		if top == 0 and bottom == 0 and (left == 0) and (right == 0):
			return []
		ans = []
		for i in range(top, bottom + 1):
			res = []
			for j in range(left, right + 1):
				res.append(a[i][j])
			ans.append(res)
		return ans


from typing import List
from typing import List

class Solution:

	def zeroSum(self, arr, final, r):
		d = {}
		maxlen = 0
		currSum = 0
		for i in range(r):
			currSum += arr[i]
			if arr[i] == 0 and maxlen == 0:
				final[0] = i
				final[1] = i
				maxlen = 1
			if currSum == 0:
				final[0] = 0
				final[1] = i
				maxlen = i + 1
			if currSum in d:
				if maxlen < i - d[currSum]:
					maxlen = i - d[currSum]
					final[0] = d[currSum] + 1
					final[1] = i
			else:
				d[currSum] = i
		return maxlen != 0

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		r = len(a)
		c = len(a[0])
		maxArea = 0
		(top, botttom, left, right) = (0, 0, 0, 0)
		prefinal = [0, 0]
		for i in range(c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(r):
					temp[k] += a[k][j]
				if self.zeroSum(temp, prefinal, r):
					area = (prefinal[1] - prefinal[0] + 1) * (j - i + 1)
					if maxArea < area:
						top = prefinal[0]
						bottom = prefinal[1]
						left = i
						right = j
						maxArea = area
		if left == 0 and right == 0 and (top == 0) and (right == 0):
			return []
		ans = []
		for i in range(top, bottom + 1):
			tmp = []
			for j in range(left, right + 1):
				tmp.append(a[i][j])
			ans.append(tmp)
		return ans


from typing import List
from typing import List
from typing import List
from typing import List

class Solution:

	def zeroSum(self, arr, final, r):
		d = {}
		maxlen = 0
		currSum = 0
		for i in range(r):
			currSum += arr[i]
			if arr[i] == 0 and maxlen == 0:
				final[0] = i
				final[1] = i
				maxlen = 1
			if currSum == 0:
				final[0] = 0
				final[1] = i
				maxlen = i + 1
			if currSum in d:
				oldl = maxlen
				maxlen = max(maxlen, i - d[currSum])
				if maxlen > oldl:
					final[0] = d[currSum] + 1
					final[1] = i
			else:
				d[currSum] = i
		return maxlen != 0

	def sumZeroMatrix(self, a: List[List[int]]) -> List[List[int]]:
		r = len(a)
		c = len(a[0])
		maxArea = 0
		(top, botttom, left, right) = (0, 0, 0, 0)
		prefinal = [0, 0]
		for i in range(c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(r):
					temp[k] += a[k][j]
				if self.zeroSum(temp, prefinal, r):
					area = (prefinal[1] - prefinal[0] + 1) * (j - i + 1)
					if maxArea < area:
						top = prefinal[0]
						bottom = prefinal[1]
						left = i
						right = j
						maxArea = area
		if left == 0 and right == 0 and (top == 0) and (right == 0):
			return []
		res = [[0 for j in range(right - left + 1)] for i in range(bottom - top + 1)]
		x = 0
		for i in range(top, bottom + 1):
			y = 0
			for j in range(left, right + 1):
				res[x][y] = a[i][j]
				y += 1
			x += 1
		return res