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:
- Create a helper function to print a matrix.
- Create a function to find the largest submatrix with zero sum:
- Initialize variables to store the resultant submatrix's row and column indices, sum, and maximum size.
- Create an auxiliary array to store the sum of elements in each row of the prefix matrix.
- Create a prefix sum matrix where each element represents the sum of elements in its row and all columns to the left.
- Iterate over all possible pairs of columns in the matrix.
- Create a HashMap to store the sum of elements in each row up to the current pair of columns.
- Iterate over each row of the matrix:
- Calculate the sum of elements in the current row between the two columns.
- 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.
- If the sum is not present in the HashMap, add it to the HashMap.
- Print the matrix elements and the resultant submatrix if found.
- In the main function:
- Create a sample matrix.
- 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
-----------------------------
*/
task.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
// 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
-----------------------------
*/
task->zeroSumSubMatrix(matrix);
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 > ();
rowSum.Add(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[sum]);
if (size > maxSize)
{
maxSize = size;
// Get row information
r1 = rowSum[sum] + 1;
r2 = i;
// Get col information
c1 = one;
c2 = two;
}
}
else
{
rowSum.Add(sum, i);
}
}
}
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
-----------------------------
*/
task.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
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
-----------------------------
*/
$task->zeroSumSubMatrix($matrix);
}
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
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
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() :
task = SubMatrix()
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
# -----------------------------
task.zeroSumSubMatrix(matrix)
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()
task = SubMatrix.new()
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
# -----------------------------
task.zeroSumSubMatrix(matrix)
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]();
rowSum.addOne(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;
}
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
{
rowSum.addOne(sum, i);
}
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
-----------------------------
*/
task.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
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
-----------------------------
*/
task.zeroSumSubMatrix(matrix);
}
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
-----------------------------
*/
task.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
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).
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.
New Comment