Skip to main content

Largest submatrix with zero sum using dynamic programming

Here given code implementation process.

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
Last updated on by Kalkicode




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