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(NNM).
Expected Auxiliary Space: O(N*M).
Constraints:
1 <= N, M <= 100
-1000 <= mat[][] <= 1000

见题面

见题面