Largest Submatrix With Sum 0

Last Updated : 27 Feb, 2026

Given a 2D matrix mat[][] of dimension n x m, find the area of largest submatrix whose sum is 0.

Examples: 

Input: mat[][] = [[9, 7, 16, 5], [1, -6, -7, 3], [1, 8, 7, 9], [7, -2, 0, 10]]
Output: 6
Explanation:

Largest-SubMatrix-with-Sum-0


Input: mat[][] = [[1, 2, 3], [-3, -2, -1], [1, 7, 5]]
Output: 6
Explanation:

Largest-SubMatrix-with-Sum-0-2


Input: mat[][] = [[1, -1], [-1, 1]]
Output: 4
Explanation: The largest submatrix with sum 0 is [[1, -1], [-1, 1]].

Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Using four Nested Loops - O(n^4) Time and O(n^2) Space

The naive solution for this problem is to check the sum of every possible rectangle in given 2D array. For this we can use four nested loop to fix the upper row, bottom row, left column and right column of the sub matrix.
Now for each such sub matrix we can find its sum using a 2D prefix sum matrix in constant time. If this calculated sum is equal to 0 then update the maximum area found.

[Expected Approach] Using Prefix Sum - O(n^3) Time and O(n) Space

The idea is to iterate over all pairs of rows to fix the top and bottom boundaries (height) of the zero-sum submatrix. Then, for each pair, we find the maximum width such that the total sum of the submatrix is zero.

To find the width of largest submatrix with zero sum for a given top and bottom row pair:

  • For a given top-bottom pair, we compute the column-wise cumulative sum in a temporary array temp[].
  • Now find the length of Longest Subarray with 0 Sum in temp[] array.

The Length of longest subarray with 0 Sum in temp[] array will also be the width of the largest 0-sum submatrix.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

//Driver Code Ends

int maxZeroSumSubarray(vector<int> &arr)
{
    int prefSum = 0;
    int maxLength = 0;

    // Hash map to store the first
    // index of each prefix sum.
    unordered_map<int, int> mp;

    // Iterate through the array to
    // find subarrays with zero sum.
    for (int i = 0; i < arr.size(); i++)
    {
        prefSum += arr[i];

        if (prefSum == 0)
            maxLength = i + 1;

        if (mp.find(prefSum) != mp.end())
        {
            // If this prefSum repeats,
            // find subarray length.
            maxLength = max(maxLength, (i - mp[prefSum]));
        }
        else
        {
            // Only store the index of the
            // first occurrence of prefSum.
            mp[prefSum] = i;
        }
    }

    return maxLength;
}

int zeroSumSubmat(vector<vector<int>> &mat)
{
    int rows = mat.size();
    int cols = mat[0].size();
    int maxArea = 0;

    for (int i = 0; i < rows; i++)
    {

        // Temporary array to store
        // the column-wise cumulative sum.
        vector<int> temp(cols, 0);

        // Iterate over each row from i to j
        for (int j = i; j < rows; j++)
        {

            // Accumulate the column-wise
            // sum for rows between i and j.
            for (int k = 0; k < cols; k++)
                temp[k] += mat[j][k];

            // Find the longest zero-sum
            //  subarray in column sums.
            int len = maxZeroSumSubarray(temp);

            // Update the maximum area
            int curHeight = (j - i + 1);
            maxArea = max(maxArea, curHeight * len);
        }
    }

    return maxArea;
}

//Driver Code Starts

int main()
{
    vector<vector<int>> mat = {{9, 7, 16, 5},
                               {1, -6, -7, 3},
                               {1, 8, 7, 9},
                               {7, -2, 0, 10}};
    cout << zeroSumSubmat(mat) << endl;
    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.HashMap;

//Driver Code Ends

class GfG {

    static int maxZeroSumSubarray(int[] arr) {
        int prefSum = 0;
        int maxLength = 0;

        // Hash map to store the first
        // index of each prefix sum.
        HashMap<Integer, Integer> mp = new HashMap<>();

        // Iterate through the array to
        // find subarrays with zero sum.
        for (int i = 0; i < arr.length; i++) {
            prefSum += arr[i];

            if (prefSum == 0)
                maxLength = i + 1;

            if (mp.containsKey(prefSum)) {
                // If this prefSum repeats,
                // find subarray length.
                maxLength = Math.max(maxLength, (i - mp.get(prefSum)));
            } else {
                // Only store the index of the
                // first occurrence of prefSum.
                mp.put(prefSum, i);
            }
        }

        return maxLength;
    }

    static int zeroSumSubmat(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {

            // Temporary array to store
            // the column-wise cumulative sum.
            int[] temp = new int[cols];

            // Iterate over each row from i to j
            for (int j = i; j < rows; j++) {

                // Accumulate the column-wise
                // sum for rows between i and j.
                for (int k = 0; k < cols; k++)
                    temp[k] += mat[j][k];

                // Find the longest zero-sum
                //  subarray in column sums.
                int len = maxZeroSumSubarray(temp);

                // Update the maximum area
                int curHeight = (j - i + 1);
                maxArea = Math.max(maxArea, curHeight * len);
            }
        }

        return maxArea;
}

//Driver Code Starts

    public static void main(String[] args) {
        int[][] mat = {
            {9, 7, 16, 5},
            {1, -6, -7, 3},
            {1, 8, 7, 9},
            {7, -2, 0, 10}
        };

        System.out.println(zeroSumSubmat(mat));
    }
}
//Driver Code Ends
Python 
def maxZeroSumSubarray(arr):
    prefSum = 0
    maxLength = 0

    # Hash map to store the first
    # index of each prefix sum.
    mp = {}

    # Iterate through the array to
    # find subarrays with zero sum.
    for i in range(len(arr)):
        prefSum += arr[i]

        if prefSum == 0:
            maxLength = i + 1

        if prefSum in mp:
            # If this prefSum repeats,
            # find subarray length.
            maxLength = max(maxLength, (i - mp[prefSum]))
        else:
            # Only store the index of the
            # first occurrence of prefSum.
            mp[prefSum] = i

    return maxLength


def zeroSumSubmat(mat):
    rows = len(mat)
    cols = len(mat[0])
    maxArea = 0

    for i in range(rows):

        # Temporary array to store
        # the column-wise cumulative sum.
        temp = [0] * cols

        # Iterate over each row from i to j
        for j in range(i, rows):

            # Accumulate the column-wise
            # sum for rows between i and j.
            for k in range(cols):
                temp[k] += mat[j][k]

            # Find the longest zero-sum
            #  subarray in column sums.
            len_sub = maxZeroSumSubarray(temp)

            # Update the maximum area
            curHeight = (j - i + 1)
            maxArea = max(maxArea, curHeight * len_sub)

    return maxArea

if __name__ == '__main__':
    mat = [
        [9, 7, 16, 5], 
        [1, -6, -7, 3], 
        [1, 8, 7, 9], 
        [7, -2, 0, 10]
    ]
    print(zeroSumSubmat(mat))
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

//Driver Code Ends

class GfG
{
    static int MaxZeroSumSubarray(int[] arr)
    {
        int prefSum = 0;
        int maxLength = 0;

        // Hash map to store the first
        // index of each prefix sum.
        Dictionary<int, int> mp = new Dictionary<int, int>();

        // Iterate through the array to
        // find subarrays with zero sum.
        for (int i = 0; i < arr.Length; i++)
        {
            prefSum += arr[i];

            if (prefSum == 0)
                maxLength = i + 1;

            if (mp.ContainsKey(prefSum))
            {
                // If this prefSum repeats,
                // find subarray length.
                maxLength = Math.Max(maxLength, (i - mp[prefSum]));
            }
            else
            {
                // Only store the index of the
                // first occurrence of prefSum.
                mp[prefSum] = i;
            }
        }

        return maxLength;
    }

    static int ZeroSumSubmat(int[,] mat)
    {
        int rows = mat.GetLength(0);
        int cols = mat.GetLength(1);
        int maxArea = 0;

        for (int i = 0; i < rows; i++)
        {
            // Temporary array to store
            // the column-wise cumulative sum.
            int[] temp = new int[cols];

            // Iterate over each row from i to j
            for (int j = i; j < rows; j++)
            {
                // Accumulate the column-wise
                // sum for rows between i and j.
                for (int k = 0; k < cols; k++)
                    temp[k] += mat[j, k];

                // Find the longest zero-sum
                //  subarray in column sums.
                int len = MaxZeroSumSubarray(temp);

                // Update the maximum area
                int curHeight = (j - i + 1);
                maxArea = Math.Max(maxArea, curHeight * len);
            }
        }

        return maxArea;
}

//Driver Code Starts

    static void Main()
    {
        int[,] mat = {
            {9, 7, 16, 5},
            {1, -6, -7, 3},
            {1, 8, 7, 9},
            {7, -2, 0, 10}
        };

        Console.WriteLine(ZeroSumSubmat(mat));
    }
}

//Driver Code Ends
JavaScript 
function maxZeroSumSubarray(arr) {
    let prefSum = 0;
    let maxLength = 0;

    // Hash map to store the first
    // index of each prefix sum.
    let mp = new Map();

    // Iterate through the array to
    // find subarrays with zero sum.
    for (let i = 0; i < arr.length; i++) {
        prefSum += arr[i];

        if (prefSum === 0)
            maxLength = i + 1;

        if (mp.has(prefSum)) {
            // If this prefSum repeats,
            // find subarray length.
            maxLength = Math.max(maxLength, (i - mp.get(prefSum)));
        } else {
            // Only store the index of the
            // first occurrence of prefSum.
            mp.set(prefSum, i);
        }
    }

    return maxLength;
}

function zeroSumSubmat(mat) {
    let rows = mat.length;
    let cols = mat[0].length;
    let maxArea = 0;

    for (let i = 0; i < rows; i++) {

        // Temporary array to store
        // the column-wise cumulative sum.
        let temp = new Array(cols).fill(0);

        // Iterate over each row from i to j
        for (let j = i; j < rows; j++) {

            // Accumulate the column-wise
            // sum for rows between i and j.
            for (let k = 0; k < cols; k++)
                temp[k] += mat[j][k];

            // Find the longest zero-sum
            //  subarray in column sums.
            let len = maxZeroSumSubarray(temp);

            // Update the maximum area
            let curHeight = (j - i + 1);
            maxArea = Math.max(maxArea, curHeight * len);
        }
    }

    return maxArea;
}

// Driver code
let mat = [
    [9, 7, 16, 5],
    [1, -6, -7, 3],
    [1, 8, 7, 9],
    [7, -2, 0, 10]
];

console.log(zeroSumSubmat(mat));

Output
6
Comment
Article Tags:
Dynamic Programming
Matrix
DSA

Explore