Posted on by Kalkicode
Code Dynamic Programming

# Largest submatrix with zero sum using dynamic programming

This article discusses the problem of finding the largest submatrix with a zero sum in a given matrix. The problem is solved using dynamic programming in Java.

## Problem Statement

Given a matrix of integers, we need to find the largest submatrix (contiguous rows and columns) that has a zero sum. The task is to find the dimensions of this submatrix and print its elements.

## Algorithm

The algorithm to find the largest submatrix with zero sum using dynamic programming consists of the following steps:

1. Create a helper function to print a matrix.
2. Create a function to find the largest submatrix with zero sum:
1. Initialize variables to store the resultant submatrix's row and column indices, sum, and maximum size.
2. Create an auxiliary array to store the sum of elements in each row of the prefix matrix.
3. Create a prefix sum matrix where each element represents the sum of elements in its row and all columns to the left.
4. Iterate over all possible pairs of columns in the matrix.
5. Create a HashMap to store the sum of elements in each row up to the current pair of columns.
6. Iterate over each row of the matrix:
1. Calculate the sum of elements in the current row between the two columns.
2. If the sum is already present in the HashMap, calculate the size of the submatrix and update the maximum size and resultant indices if necessary.
3. If the sum is not present in the HashMap, add it to the HashMap.
7. Print the matrix elements and the resultant submatrix if found.
3. In the main function:
1. Create a sample matrix.
2. Create an instance of the SubMatrix class and call the zeroSumSubMatrix function.

## Code Solution

``````import java.util.HashMap;
/*
Java Program for
Largest submatrix with zero sum using dynamic programming
*/
public class SubMatrix
{
public void printMatrix(int[][] matrix)
{
int n = matrix.length;
int m = matrix[0].length;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
System.out.print("   " + matrix[i][j]);
}
System.out.print("\n");
}
}
public void zeroSumSubMatrix(int[][] matrix)
{
int n = matrix.length;
int m = matrix[0].length;
// Resultant column
int c1 = 0;
int c2 = 0;
// Resultant row
int r1 = 0;
int r2 = 0;
int sum = 0;
int maxSize = 0;
int auxiliary[] = new int[n];
int[][] prefixSum = new int[n][m];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
prefixSum[i][j] = matrix[i][j];
}
}
// calculation prefix sum for each row
for (int i = 0; i < n; ++i)
{
for (int j = 1; j < m; ++j)
{
prefixSum[i][j] += prefixSum[i][j - 1];
}
}
for (int one = 0; one < m; ++one)
{
for (int two = one; two < m; ++two)
{
HashMap < Integer, Integer > rowSum =
new HashMap < Integer, Integer > ();

rowSum.put(0, -1);

for (int row = 0; row < n; ++row)
{

if(one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}

}
for (int i = 0; i < n; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.containsKey(sum))
{
int size = (two - one + 1) * (i - rowSum.get(sum));
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.get(sum) + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.put(sum, i);
}
}
}
sum = 0;
}
// Print matrix elements
printMatrix(matrix);
if (maxSize == 0)
{
System.out.print("\n No Result\n");
}
else
{
System.out.print("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for (int i = r1; i <= r2; i++)
{
for (int j = c1; j <= c2; j++)
{
System.out.print("  " + matrix[i][j]);
}
System.out.print("\n");
}
}
}
public static void main(String[] args)
{
SubMatrix task = new SubMatrix();
int[][] matrix = {
{
1 , 10 , -4 , 15 , -5 , 4
},
{
2 , -5 , 4 , 3 , 1 , -5
},
{
3 , -3 , -7 , -3 , 2 , 8
},
{
4 , 1 , -4 , 7 , -8 , 3
},
{
2 , -1 , 5 , 6 , -3 , 8
}
};
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8

size = 12
sum = 0
-----------------------------
*/
}
}``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````
``````// Include header file
#include <iostream>

#include <unordered_map>
#define N 5
#define M 6
using namespace std;
/*
C++ Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
public: void printMatrix(int matrix[N][M])
{

for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
cout << "   " << matrix[i][j];
}
cout << "\n";
}
}
void zeroSumSubMatrix(int matrix[N][M])
{

// Resultant column
int c1 = 0;
int c2 = 0;
// Resultant row
int r1 = 0;
int r2 = 0;
int sum = 0;
int maxSize = 0;
int auxiliary[N];
int prefixSum[N][M];
unordered_map < int, int > rowSum;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
prefixSum[i][j] = matrix[i][j];
}
}
// calculation prefix sum for each row
for (int i = 0; i < N; ++i)
{
for (int j = 1; j < M; ++j)
{
prefixSum[i][j] += prefixSum[i][j - 1];
}
}

for (int one = 0; one < M; ++one)
{
for (int two = one; two < M; ++two)
{

rowSum[0] = -1;
for (int row = 0; row < N; ++row)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
}
for (int i = 0; i < N; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.find(sum) != rowSum.end())
{
int size = (two - one + 1) *(i - rowSum[sum]);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum[sum] + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum[sum] = i;
}
}
}
rowSum.clear();
sum = 0;
}
// Print matrix elements
this->printMatrix(matrix);
if (maxSize == 0)
{
cout << "\n No Result\n";
}
else
{
cout << "\n Resultant Sub Matrix\n";
// Print resultant submatrix
for (int i = r1; i <= r2; i++)
{
for (int j = c1; j <= c2; j++)
{
cout << "  " << matrix[i][j];
}
cout << "\n";
}
}
}
};
int main()
{
SubMatrix *task = new SubMatrix();
int matrix[N][M] = {
{
1 , 10 , -4 , 15 , -5 , 4
} , {
2 , -5 , 4 , 3 , 1 , -5
} , {
3 , -3 , -7 , -3 , 2 , 8
} , {
4 , 1 , -4 , 7 , -8 , 3
} , {
2 , -1 , 5 , 6 , -3 , 8
}
};
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
return 0;
}``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program for
Largest submatrix with zero sum using dynamic programming
*/
public class SubMatrix
{
public void printMatrix(int[,] matrix)
{
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
Console.Write("   " + matrix[i,j]);
}
Console.Write("\n");
}
}
public void zeroSumSubMatrix(int[,] matrix)
{
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
// Resultant column
int c1 = 0;
int c2 = 0;
// Resultant row
int r1 = 0;
int r2 = 0;
int sum = 0;
int maxSize = 0;
int[] auxiliary = new int[n];
int[,] prefixSum = new int[n,m];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
prefixSum[i,j] = matrix[i,j];
}
}
// calculation prefix sum for each row
for (int i = 0; i < n; ++i)
{
for (int j = 1; j < m; ++j)
{
prefixSum[i,j] += prefixSum[i,j - 1];
}
}
for (int one = 0; one < m; ++one)
{
for (int two = one; two < m; ++two)
{
Dictionary < int, int > rowSum =
new Dictionary < int, int > ();
for (int row = 0; row < n; ++row)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row,two] -
prefixSum[row,one - 1];
}
else
{
auxiliary[row] = prefixSum[row,two];
}
}
for (int i = 0; i < n; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.ContainsKey(sum))
{
int size = (two - one + 1) * (i - rowSum[sum]);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum[sum] + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
}
}
}
sum = 0;
}
// Print matrix elements
this.printMatrix(matrix);
if (maxSize == 0)
{
Console.Write("\n No Result\n");
}
else
{
Console.Write("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for (int i = r1; i <= r2; i++)
{
for (int j = c1; j <= c2; j++)
{
Console.Write("  " + matrix[i,j]);
}
Console.Write("\n");
}
}
}
public static void Main(String[] args)
{
SubMatrix task = new SubMatrix();
int[,] matrix = {
{
1 , 10 , -4 , 15 , -5 , 4
},
{
2 , -5 , 4 , 3 , 1 , -5
},
{
3 , -3 , -7 , -3 , 2 , 8
},
{
4 , 1 , -4 , 7 , -8 , 3
},
{
2 , -1 , 5 , 6 , -3 , 8
}
};
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
}
}``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````
``````package main
import "fmt"
/*
Go Program for
Largest submatrix with zero sum using dynamic programming
*/

func printMatrix(matrix[][] int) {
var n int = len(matrix)
var m int = len(matrix[0])
for i := 0 ; i < n ; i++ {
for j := 0 ; j < m ; j++ {
fmt.Print("   ", matrix[i][j])
}
fmt.Print("\n")
}
}
func zeroSumSubMatrix(matrix[][] int) {
var n int = len(matrix)
var m int = len(matrix[0])
// Resultant column
var c1 int = 0
var c2 int = 0
// Resultant row
var r1 int = 0
var r2 int = 0
var sum int = 0
var maxSize int = 0
var auxiliary = make([] int, n)
var prefixSum = make([][] int, n)
for i := 0; i < n; i++ {
prefixSum[i] = make([]int,m)
}
for i := 0 ; i < n ; i++ {
for j := 0 ; j < m ; j++ {
prefixSum[i][j] = matrix[i][j]
}
}
// calculation prefix sum for each row
for i := 0 ; i < n ; i++ {
for j := 1 ; j < m ; j++ {
prefixSum[i][j] += prefixSum[i][j - 1]
}
}
for one := 0 ; one < m ; one++ {
for two := one ; two < m ; two++ {
var rowSum = make(map[int] int)
rowSum[0] = -1
for row := 0 ; row < n ; row++ {
if one > 0 {
auxiliary[row] = prefixSum[row][two] - prefixSum[row][one - 1]
} else {
auxiliary[row] = prefixSum[row][two]
}
}
for i := 0 ; i < n ; i++ {
sum = sum + auxiliary[i]
if _, found := rowSum[sum] ; found {
var size int = (two - one + 1) * (i - rowSum[sum])
if size > maxSize {
maxSize = size
// Get row information
r1 = rowSum[sum] + 1
r2 = i
// Get col information
c1 = one
c2 = two
}
} else {
rowSum[sum] = i
}
}
}
sum = 0
}
// Print matrix elements
printMatrix(matrix)
if maxSize == 0 {
fmt.Print("\n No Result\n")
} else {
fmt.Print("\n Resultant Sub Matrix\n")
// Print resultant submatrix
for i := r1 ; i <= r2 ; i++ {
for j := c1 ; j <= c2 ; j++ {
fmt.Print("  ", matrix[i][j])
}
fmt.Print("\n")
}
}
}
func main() {

var matrix = [][] int {
{1,  10,   -4,  15, -5,  4},
{2,  -5,    4,  3,  1, -5},
{3,  -3 ,  -7, -3,  2,  8},
{4,   1,   -4,  7, -8,  3},
{2,  -1,    5,  6, -3,  8}}
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
zeroSumSubMatrix(matrix)
}``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````
``````<?php
/*
Php Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
public	function printMatrix(\$matrix)
{
\$n = count(\$matrix);
\$m = count(\$matrix[0]);
for (\$i = 0; \$i < \$n; ++\$i)
{
for (\$j = 0; \$j < \$m; ++\$j)
{
echo("   ".\$matrix[\$i][\$j]);
}
echo("\n");
}
}
public	function zeroSumSubMatrix(\$matrix)
{
\$n = count(\$matrix);
\$m = count(\$matrix[0]);
// Resultant column
\$c1 = 0;
\$c2 = 0;
// Resultant row
\$r1 = 0;
\$r2 = 0;
\$sum = 0;
\$maxSize = 0;
\$auxiliary = array_fill(0, \$n, 0);
\$prefixSum = array_fill(0, \$n, array_fill(0, \$m, 0));
for (\$i = 0; \$i < \$n; ++\$i)
{
for (\$j = 0; \$j < \$m; ++\$j)
{
\$prefixSum[\$i][\$j] = \$matrix[\$i][\$j];
}
}
// calculation prefix sum for each row
for (\$i = 0; \$i < \$n; ++\$i)
{
for (\$j = 1; \$j < \$m; ++\$j)
{
\$prefixSum[\$i][\$j] += \$prefixSum[\$i][\$j - 1];
}
}
for (\$one = 0; \$one < \$m; ++\$one)
{
for (\$two = \$one; \$two < \$m; ++\$two)
{
\$rowSum = array();
\$rowSum[0] = -1;
for (\$row = 0; \$row < \$n; ++\$row)
{
if (\$one > 0)
{
\$auxiliary[\$row] = \$prefixSum[\$row][\$two] -
\$prefixSum[\$row][\$one - 1];
}
else
{
\$auxiliary[\$row] = \$prefixSum[\$row][\$two];
}
}
for (\$i = 0; \$i < \$n; ++\$i)
{
\$sum = \$sum + \$auxiliary[\$i];
if (array_key_exists(\$sum, \$rowSum))
{
\$size = (\$two - \$one + 1) * (\$i - \$rowSum[\$sum]);
if (\$size > \$maxSize)
{
\$maxSize = \$size;
// Get row information
\$r1 = \$rowSum[\$sum] + 1;
\$r2 = \$i;
// Get col information
\$c1 = \$one;
\$c2 = \$two;
}
}
else
{
\$rowSum[\$sum] = \$i;
}
}
}
\$sum = 0;
}
// Print matrix elements
\$this->printMatrix(\$matrix);
if (\$maxSize == 0)
{
echo("\n No Result\n");
}
else
{
echo("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for (\$i = \$r1; \$i <= \$r2; \$i++)
{
for (\$j = \$c1; \$j <= \$c2; \$j++)
{
echo("  ".\$matrix[\$i][\$j]);
}
echo("\n");
}
}
}
}

function main()
{
\$task = new SubMatrix();
\$matrix = array(
array(1, 10, -4, 15, -5, 4),
array(2, -5, 4, 3, 1, -5),
array(3, -3, -7, -3, 2, 8),
array(4, 1, -4, 7, -8, 3),
array(2, -1, 5, 6, -3, 8)
);
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
}
main();``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````
``````/*
Node JS Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
printMatrix(matrix)
{
var n = matrix.length;
var m = matrix[0].length;
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < m; ++j)
{
process.stdout.write("   " + matrix[i][j]);
}
process.stdout.write("\n");
}
}
zeroSumSubMatrix(matrix)
{
var n = matrix.length;
var m = matrix[0].length;
// Resultant column
var c1 = 0;
var c2 = 0;
// Resultant row
var r1 = 0;
var r2 = 0;
var sum = 0;
var maxSize = 0;
var auxiliary = Array(n).fill(0);
var prefixSum = Array(n).fill(0).map(() => new Array(m).fill(0));
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < m; ++j)
{
prefixSum[i][j] = matrix[i][j];
}
}
// calculation prefix sum for each row
for (var i = 0; i < n; ++i)
{
for (var j = 1; j < m; ++j)
{
prefixSum[i][j] += prefixSum[i][j - 1];
}
}
for (var one = 0; one < m; ++one)
{
for (var two = one; two < m; ++two)
{
var rowSum = new Map();
rowSum.set(0, -1);
for (var row = 0; row < n; ++row)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] - prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
}
for (var i = 0; i < n; ++i)
{
sum = sum + auxiliary[i];
if (rowSum.has(sum))
{
var size = (two - one + 1) * (i - rowSum.get(sum));
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.get(sum) + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.set(sum, i);
}
}
}
sum = 0;
}
// Print matrix elements
this.printMatrix(matrix);
if (maxSize == 0)
{
process.stdout.write("\n No Result\n");
}
else
{
process.stdout.write("\n Resultant Sub Matrix\n");
// Print resultant submatrix
for (var i = r1; i <= r2; i++)
{
for (var j = c1; j <= c2; j++)
{
process.stdout.write("  " + matrix[i][j]);
}
process.stdout.write("\n");
}
}
}
}

function main()
{
var task = new SubMatrix();
var matrix = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
];
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
}
main();``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````
``````#    Python 3 Program for
#    Largest submatrix with zero sum using dynamic programming
class SubMatrix :
def printMatrix(self, matrix) :
n = len(matrix)
m = len(matrix[0])
i = 0
while (i < n) :
j = 0
while (j < m) :
print("   ", matrix[i][j], end = "")
j += 1

print(end = "\n")
i += 1

def zeroSumSubMatrix(self, matrix) :
n = len(matrix)
m = len(matrix[0])
#  Resultant column
c1 = 0
c2 = 0
#  Resultant row
r1 = 0
r2 = 0
sum = 0
maxSize = 0
auxiliary = [0] * (n)
prefixSum = [[0] * (m) for _ in range(n) ]
i = 0
while (i < n) :
j = 0
while (j < m) :
prefixSum[i][j] = matrix[i][j]
j += 1

i += 1

i = 0
#  calculation prefix sum for each row
while (i < n) :
j = 1
while (j < m) :
prefixSum[i][j] += prefixSum[i][j - 1]
j += 1

i += 1

one = 0
while (one < m) :
two = one
while (two < m) :
rowSum = dict()
rowSum[0] = -1
row = 0
while (row < n) :
if (one > 0) :
auxiliary[row] = prefixSum[row][two] - prefixSum[row][one - 1]
else :
auxiliary[row] = prefixSum[row][two]

row += 1

i = 0
while (i < n) :
sum = sum + auxiliary[i]
if ((sum in rowSum.keys())) :
size = (two - one + 1) * (i - rowSum.get(sum))
if (size > maxSize) :
maxSize = size
#  Get row information
r1 = rowSum.get(sum) + 1
r2 = i
#  Get col information
c1 = one
c2 = two

else :
rowSum[sum] = i

i += 1

two += 1

sum = 0
one += 1

#  Print matrix elements
self.printMatrix(matrix)
if (maxSize == 0) :
print("\n No Result")
else :
print("\n Resultant Sub Matrix")
i = r1
#  Print resultant submatrix
while (i <= r2) :
j = c1
while (j <= c2) :
print("  ", matrix[i][j], end = "")
j += 1

print(end = "\n")
i += 1

def main() :
matrix = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
]
#    marix =
#    [
#        [1,  10,   -4,  15, -5,  4]
#        [2,  -5,    4,  3,  1, -5]
#        [3,  -3 ,  -7, -3,  2,  8]
#        [4,   1,   -4,  7, -8,  3]
#        [2,  -1,    5,  6, -3,  8]
#    ]
#    -----------------------------------
#    Output
#    [
#        [ 2 -5 4 3 1 -5 ]
#        [ 3 -3 -7 -3 2 8 ]
#    ]
#    Resultant sub matrix
#    --------------------------
#    2 + (-5) + 4 + 3 + 1 + (-5) +
#    3 + (-3) + (-7) + (-3) + 2 + 8
#    size = 12
#    sum = 0
#    -----------------------------

if __name__ == "__main__": main()``````

#### Output

``````    1    10    -4    15    -5    4
2    -5    4    3    1    -5
3    -3    -7    -3    2    8
4    1    -4    7    -8    3
2    -1    5    6    -3    8

Resultant Sub Matrix
2   -5   4   3   1   -5
3   -3   -7   -3   2   8``````
``````#    Ruby Program for
#    Largest submatrix with zero sum using dynamic programming
class SubMatrix
def printMatrix(matrix)
n = matrix.length
m = matrix[0].length
i = 0
while (i < n)
j = 0
while (j < m)
print("   ", matrix[i][j])
j += 1
end

print("\n")
i += 1
end

end

def zeroSumSubMatrix(matrix)
n = matrix.length
m = matrix[0].length
#  Resultant column
c1 = 0
c2 = 0
#  Resultant row
r1 = 0
r2 = 0
sum = 0
maxSize = 0
auxiliary = Array.new(n) {0}
prefixSum = Array.new(n) {Array.new(m) {0}}
i = 0
while (i < n)
j = 0
while (j < m)
prefixSum[i][j] = matrix[i][j]
j += 1
end

i += 1
end

i = 0
#  calculation prefix sum for each row
while (i < n)
j = 1
while (j < m)
prefixSum[i][j] += prefixSum[i][j - 1]
j += 1
end

i += 1
end

one = 0
while (one < m)
two = one
while (two < m)
rowSum = Hash.new()
rowSum[0] = -1
row = 0
while (row < n)
if (one > 0)
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1]
else

auxiliary[row] = prefixSum[row][two]
end

row += 1
end

i = 0
while (i < n)
sum = sum + auxiliary[i]
if (rowSum.key?(sum))
size = (two - one + 1) * (i - rowSum[sum])
if (size > maxSize)
maxSize = size
#  Get row information
r1 = rowSum[sum] + 1
r2 = i
#  Get col information
c1 = one
c2 = two
end

else

rowSum[sum] = i
end

i += 1
end

two += 1
end

sum = 0
one += 1
end

#  Print matrix elements
self.printMatrix(matrix)
if (maxSize == 0)
print("\n No Result\n")
else

print("\n Resultant Sub Matrix\n")
i = r1
#  Print resultant submatrix
while (i <= r2)
j = c1
while (j <= c2)
print("  ", matrix[i][j])
j += 1
end

print("\n")
i += 1
end

end

end

end

def main()
matrix = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
]
#    marix =
#    [
#        [1,  10,   -4,  15, -5,  4]
#        [2,  -5,    4,  3,  1, -5]
#        [3,  -3 ,  -7, -3,  2,  8]
#        [4,   1,   -4,  7, -8,  3]
#        [2,  -1,    5,  6, -3,  8]
#    ]
#    -----------------------------------
#    Output
#    [
#        [ 2 -5 4 3 1 -5 ]
#        [ 3 -3 -7 -3 2 8 ]
#    ]
#    Resultant sub matrix
#    --------------------------
#    2 + (-5) + 4 + 3 + 1 + (-5) +
#    3 + (-3) + (-7) + (-3) + 2 + 8
#    size = 12
#    sum = 0
#    -----------------------------
end

main()``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8
``````
``````import scala.collection.mutable._;
/*
Scala Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix()
{
def printMatrix(matrix: Array[Array[Int]]): Unit = {
var n: Int = matrix.length;
var m: Int = matrix(0).length;
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
print("   " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
def zeroSumSubMatrix(matrix: Array[Array[Int]]): Unit = {
var n: Int = matrix.length;
var m: Int = matrix(0).length;
// Resultant column
var c1: Int = 0;
var c2: Int = 0;
// Resultant row
var r1: Int = 0;
var r2: Int = 0;
var sum: Int = 0;
var maxSize: Int = 0;
var auxiliary: Array[Int] = Array.fill[Int](n)(0);
var prefixSum: Array[Array[Int]] = Array.fill[Int](n, m)(0);
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
prefixSum(i)(j) = matrix(i)(j);
j += 1;
}
i += 1;
}
i = 0;
// calculation prefix sum for each row
while (i < n)
{
var j: Int = 1;
while (j < m)
{
prefixSum(i)(j) += prefixSum(i)(j - 1);
j += 1;
}
i += 1;
}
var one: Int = 0;
while (one < m)
{
var two: Int = one;
while (two < m)
{
var rowSum: HashMap[Int, Int] = new HashMap[Int, Int]();
var row: Int = 0;
while (row < n)
{
if (one > 0)
{
auxiliary(row) = prefixSum(row)(two) -
prefixSum(row)(one - 1);
}
else
{
auxiliary(row) = prefixSum(row)(two);
}
row += 1;
}
var i: Int = 0;
while (i < n)
{
sum = sum + auxiliary(i);
if (rowSum.contains(sum))
{
var size: Int = (two - one + 1) *
(i - rowSum.get(sum).get);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.get(sum).get + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
}
i += 1;
}
two += 1;
}
sum = 0;
one += 1;
}
// Print matrix elements
printMatrix(matrix);
if (maxSize == 0)
{
print("\n No Result\n");
}
else
{
print("\n Resultant Sub Matrix\n");
i = r1;
// Print resultant submatrix
while (i <= r2)
{
var j: Int = c1;
while (j <= c2)
{
print("  " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubMatrix = new SubMatrix();
var matrix: Array[Array[Int]] = Array(Array(1, 10, -4, 15, -5, 4), Array(2, -5, 4, 3, 1, -5), Array(3, -3, -7, -3, 2, 8), Array(4, 1, -4, 7, -8, 3), Array(2, -1, 5, 6, -3, 8));
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
}
}``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````
``````import Foundation;
/*
Swift 4 Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
func printMatrix(_ matrix: [[Int]])
{
let n: Int = matrix.count;
let m: Int = matrix[0].count;
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
print("   ", matrix[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
func zeroSumSubMatrix(_ matrix: [[Int]])
{
let n: Int = matrix.count;
let m: Int = matrix[0].count;
// Resultant column
var c1: Int = 0;
var c2: Int = 0;
// Resultant row
var r1: Int = 0;
var r2: Int = 0;
var sum: Int = 0;
var maxSize: Int = 0;
var auxiliary: [Int] = Array(repeating: 0, count: n);
var prefixSum: [[Int]] =
Array(repeating: Array(repeating: 0, count: m), count: n);
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
prefixSum[i][j] = matrix[i][j];
j += 1;
}
i += 1;
}
i = 0;
// calculation prefix sum for each row
while (i < n)
{
var j: Int = 1;
while (j < m)
{
prefixSum[i][j] += prefixSum[i][j - 1];
j += 1;
}
i += 1;
}
var one: Int = 0;
while (one < m)
{
var two: Int = one;
while (two < m)
{
var rowSum = [Int : Int]();
rowSum[0] = -1;
var row: Int = 0;
while (row < n)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
row += 1;
}
i = 0;
while (i < n)
{
sum = sum + auxiliary[i];
if (rowSum.keys.contains(sum))
{
let size: Int = (two - one + 1) * (i - rowSum[sum]!);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum[sum]! + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum[sum] = i;
}
i += 1;
}
two += 1;
}
sum = 0;
one += 1;
}
// Print matrix elements
self.printMatrix(matrix);
if (maxSize == 0)
{
print("\n No Result");
}
else
{
print("\n Resultant Sub Matrix");
i = r1;
// Print resultant submatrix
while (i <= r2)
{
var j: Int = c1;
while (j <= c2)
{
print("  ", matrix[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
}
}
func main()
{
let task: SubMatrix = SubMatrix();
let matrix: [
[Int]
] = [
[1, 10, -4, 15, -5, 4],
[2, -5, 4, 3, 1, -5],
[3, -3, -7, -3, 2, 8],
[4, 1, -4, 7, -8, 3],
[2, -1, 5, 6, -3, 8]
];
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
}
main();``````

#### Output

``````    1    10    -4    15    -5    4
2    -5    4    3    1    -5
3    -3    -7    -3    2    8
4    1    -4    7    -8    3
2    -1    5    6    -3    8

Resultant Sub Matrix
2   -5   4   3   1   -5
3   -3   -7   -3   2   8``````
``````/*
Kotlin Program for
Largest submatrix with zero sum using dynamic programming
*/
class SubMatrix
{
fun printMatrix(matrix: Array < Array < Int >> ): Unit
{
val n: Int = matrix.count();
val m: Int = matrix[0].count();
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
print("   " + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
}
fun zeroSumSubMatrix(matrix: Array < Array < Int >> ): Unit
{
val n: Int = matrix.count();
val m: Int = matrix[0].count();
// Resultant column
var c1: Int = 0;
var c2: Int = 0;
// Resultant row
var r1: Int = 0;
var r2: Int = 0;
var sum: Int = 0;
var maxSize: Int = 0;
var auxiliary: Array < Int > = Array(n)
{
0
};
var prefixSum: Array < Array < Int >> = Array(n)
{
Array(m)
{
0
}
};
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
prefixSum[i][j] = matrix[i][j];
j += 1;
}
i += 1;
}
i = 0;
// calculation prefix sum for each row
while (i < n)
{
var j: Int = 1;
while (j < m)
{
prefixSum[i][j] += prefixSum[i][j - 1];
j += 1;
}
i += 1;
}
var one: Int = 0;
while (one < m)
{
var two: Int = one;
while (two < m)
{
val rowSum: HashMap < Int, Int > = HashMap < Int, Int > ();
rowSum.put(0, -1);
var row: Int = 0;
while (row < n)
{
if (one > 0)
{
auxiliary[row] = prefixSum[row][two] -
prefixSum[row][one - 1];
}
else
{
auxiliary[row] = prefixSum[row][two];
}
row += 1;
}
i = 0;
while (i < n)
{
sum = sum + auxiliary[i];
if (rowSum.containsKey(sum))
{
val size: Int = (two - one + 1) *
(i - rowSum.getValue(sum));
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum.getValue(sum) + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.put(sum, i);
}
i += 1;
}
two += 1;
}
sum = 0;
one += 1;
}
// Print matrix elements
this.printMatrix(matrix);
if (maxSize == 0)
{
print("\n No Result\n");
}
else
{
print("\n Resultant Sub Matrix\n");
i = r1;
// Print resultant submatrix
while (i <= r2)
{
var j: Int = c1;
while (j <= c2)
{
print("  " + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
val task: SubMatrix = SubMatrix();
val matrix: Array < Array < Int >> = arrayOf(arrayOf(1, 10, -4, 15, -5, 4), arrayOf(2, -5, 4, 3, 1, -5), arrayOf(3, -3, -7, -3, 2, 8), arrayOf(4, 1, -4, 7, -8, 3), arrayOf(2, -1, 5, 6, -3, 8));
/*
marix =
[
[1,  10,   -4,  15, -5,  4]
[2,  -5,    4,  3,  1, -5]
[3,  -3 ,  -7, -3,  2,  8]
[4,   1,   -4,  7, -8,  3]
[2,  -1,    5,  6, -3,  8]
]
-----------------------------------
Output
[
[ 2 -5 4 3 1 -5 ]
[ 3 -3 -7 -3 2 8 ]
]
Resultant sub matrix
--------------------------
2 + (-5) + 4 + 3 + 1 + (-5) +
3 + (-3) + (-7) + (-3) + 2 + 8
size = 12
sum = 0
-----------------------------
*/
}``````

#### Output

``````   1   10   -4   15   -5   4
2   -5   4   3   1   -5
3   -3   -7   -3   2   8
4   1   -4   7   -8   3
2   -1   5   6   -3   8

Resultant Sub Matrix
2  -5  4  3  1  -5
3  -3  -7  -3  2  8``````

## Resultant Output Explanation

The given matrix is as follows:

```     1  10  -4  15  -5   4
2  -5   4   3   1  -5
3  -3  -7  -3   2   8
4   1  -4   7  -8   3
2  -1   5   6  -3   8
```

The output shows the resultant submatrix with a zero sum:

```    2  -5   4   3   1  -5
3  -3  -7  -3   2   8
```

The sum of all the elements in the resultant submatrix is zero. The size of the submatrix is 12 (2 rows × 6 columns). The sum is recalculated to demonstrate that it indeed evaluates to zero.

## Time Complexity

The time complexity of the algorithm is O(n^3), where n is the number of rows in the matrix. This is because we iterate over all possible pairs of columns and rows to calculate the sum of elements. The prefix sum calculation takes O(n^2) time, and the nested loops iterate over n rows and m columns, resulting in a total complexity of O(n^3).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post