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
            -----------------------------
        */
        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).

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.

New Comment





Categories
Relative Post