Horje
Find the largest area rectangular sub-matrix whose sum is equal to k

Given a 2D matrix mat[][] and a value k. Find the largest rectangular sub-matrix whose sum is equal to k. 

Example:

Input : mat = { { 1, 7, -6, 5 }, 
            { -8, 6, 7, -2 }, 
            { 10, -15, 3, 2 }, 
            { -5, 2, 0, 9 } }
        k = 7 

Output : (Top, Left): (0, 1)
         (Bottom, Right): (2, 3)
         7 -6 5 
         6 7 -2 
        -15 3 2

Brute Approach: 

The program takes in a matrix of integers and an integer value k as input, and returns the largest submatrix of the matrix whose sum is equal to k.

Algorithm

  • Initialize maxSubmatrix to an empty 2D vector and maxSize to 0.
  • Loop through all possible starting rows and columns of submatrices (let them be denoted by r and c respectively)
    i. Loop through all possible ending rows and columns of submatrices (let them be denoted by rEnd and cEnd respectively)
    i. Calculate the sum of elements in the current submatrix by looping through its rows and columns
    ii. If the sum is equal to k and the size of the submatrix is greater than maxSize, update maxSubmatrix to the current submatrix and maxSize to its size
  • Return maxSubmatrix

C++

#include <iostream>
#include <vector>
using namespace std;
 
vector<vector<int>> findLargestSubmatrixWithSumK(vector<vector<int>>& mat, int k) {
    int m = mat.size(); // number of rows in the matrix
    int n = mat[0].size(); // number of columns in the matrix
    vector<vector<int>> maxSubmatrix; // initialize the largest submatrix to an empty vector
    int maxSize = 0; // initialize the maximum size to 0
     
    // loop through all possible starting rows and columns
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            // loop through all possible ending rows and columns
            for (int rEnd = r; rEnd < m; rEnd++) {
                for (int cEnd = c; cEnd < n; cEnd++) {
                    int submatrixSum = 0; // initialize the sum of the current submatrix to 0
                    // loop through all elements of the current submatrix and add their values to the sum
                    for (int i = r; i <= rEnd; i++) {
                        for (int j = c; j <= cEnd; j++) {
                            submatrixSum += mat[i][j];
                        }
                    }
                     
                    // if the sum of the submatrix is equal to k and its size is greater than the maximum size seen so far
                    if (submatrixSum == k && (rEnd - r + 1) * (cEnd - c + 1) > maxSize) {
                        maxSubmatrix.clear(); // clear the largest submatrix vector
                        // loop through all elements of the current submatrix and add them to the largest submatrix vector
                        for (int i = r; i <= rEnd; i++) {
                            vector<int> row(mat[i].begin() + c, mat[i].begin() + cEnd + 1); // get a subvector of the current row corresponding to the current submatrix column range
                            maxSubmatrix.push_back(row); // add the row to the largest submatrix vector
                        }
                        maxSize = (rEnd - r + 1) * (cEnd - c + 1); // update the maximum size seen so far
                    }
                }
            }
        }
    }
    return maxSubmatrix; // return the largest submatrix with the desired sum
}
 
int main() {
    vector<vector<int>> mat = {{ 1, 7, -6, 5 },
                       { -8, 6, 7, -2 },
                       { 10, -15, 3, 2 },
                       { -5, 2, 0, 9 }};
    int k = 7;
    vector<vector<int>> largestSubmatrix = findLargestSubmatrixWithSumK(mat, k);
    cout << "Largest sub-matrix with sum " << k << ":\n";
    for (vector<int>& row : largestSubmatrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Java

//GFG
//Java code for this approach
import java.util.ArrayList;
 
public class Main {
    public static ArrayList<ArrayList<Integer>> findLargestSubmatrixWithSumK(int[][] mat, int k) {
        int m = mat.length; // number of rows in the matrix
        int n = mat[0].length; // number of columns in the matrix
        ArrayList<ArrayList<Integer>> maxSubmatrix = new ArrayList<>(); // initialize the largest submatrix to an empty ArrayList
        int maxSize = 0; // initialize the maximum size to 0
 
        // loop through all possible starting rows and columns
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // loop through all possible ending rows and columns
                for (int rEnd = r; rEnd < m; rEnd++) {
                    for (int cEnd = c; cEnd < n; cEnd++) {
                        int submatrixSum = 0; // initialize the sum of the current submatrix to 0
                        // loop through all elements of the current submatrix and add their values to the sum
                        for (int i = r; i <= rEnd; i++) {
                            for (int j = c; j <= cEnd; j++) {
                                submatrixSum += mat[i][j];
                            }
                        }
 
                        // if the sum of the submatrix is equal to k and its size is greater than the maximum size seen so far
                        if (submatrixSum == k && (rEnd - r + 1) * (cEnd - c + 1) > maxSize) {
                            maxSubmatrix.clear(); // clear the largest submatrix ArrayList
                            // loop through all elements of the current submatrix and add them to the largest submatrix ArrayList
                            for (int i = r; i <= rEnd; i++) {
                                ArrayList<Integer> row = new ArrayList<>();
                                for (int j = c; j <= cEnd; j++) {
                                    row.add(mat[i][j]);
                                }
                                maxSubmatrix.add(row); // add the row to the largest submatrix ArrayList
                            }
                            maxSize = (rEnd - r + 1) * (cEnd - c + 1); // update the maximum size seen so far
                        }
                    }
                }
            }
        }
        return maxSubmatrix; // return the largest submatrix with the desired sum
    }
 
    public static void main(String[] args) {
        int[][] mat = {{ 1, 7, -6, 5 },
                       { -8, 6, 7, -2 },
                       { 10, -15, 3, 2 },
                       { -5, 2, 0, 9 }};
        int k = 7;
        ArrayList<ArrayList<Integer>> largestSubmatrix = findLargestSubmatrixWithSumK(mat, k);
        System.out.println("Largest sub-matrix with sum " + k + ":");
        for (ArrayList<Integer> row : largestSubmatrix) {
            for (int val : row) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }
}
//This code is written by sundaram

Python

def findLargestSubmatrixWithSumK(mat, k):
    m = len(mat) # number of rows in the matrix
    n = len(mat[0]) # number of columns in the matrix
    maxSubmatrix = [] # initialize the largest submatrix to an empty list
    maxSize = 0 # initialize the maximum size to 0
     
    # loop through all possible starting rows and columns
    for r in range(m):
        for c in range(n):
            # loop through all possible ending rows and columns
            for rEnd in range(r, m):
                for cEnd in range(c, n):
                    submatrixSum = 0 # initialize the sum of the current submatrix to 0
                    # loop through all elements of the current submatrix and add their values to the sum
                    for i in range(r, rEnd+1):
                        for j in range(c, cEnd+1):
                            submatrixSum += mat[i][j]
                     
                    # if the sum of the submatrix is equal to k and its size is greater than the maximum size seen so far
                    if submatrixSum == k and (rEnd - r + 1) * (cEnd - c + 1) > maxSize:
                        maxSubmatrix = [] # clear the largest submatrix list
                        # loop through all elements of the current submatrix and add them to the largest submatrix list
                        for i in range(r, rEnd+1):
                            row = mat[i][c:cEnd+1] # get a sublist of the current row corresponding to the current submatrix column range
                            maxSubmatrix.append(row) # add the row to the largest submatrix list
                        maxSize = (rEnd - r + 1) * (cEnd - c + 1) # update the maximum size seen so far
     
    return maxSubmatrix # return the largest submatrix with the desired sum
 
# example usage
mat = [[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]]
k = 12
largestSubmatrix = findLargestSubmatrixWithSumK(mat, k)
print("Largest sub-matrix with sum", k, ":")
for row in largestSubmatrix:
    print(row)

C#

using System;
using System.Collections.Generic;
 
public class Program {
    public static List<List<int> >
    FindLargestSubmatrixWithSumK(int[, ] mat, int k)
    {
        int m = mat.GetLength(
            0); // number of rows in the matrix
        int n = mat.GetLength(
            1); // number of columns in the matrix
        List<List<int> > maxSubmatrix
            = new List<List<int> >(); // initialize the
                                      // largest submatrix
                                      // to an empty List
        int maxSize = 0; // initialize the maximum size to 0
 
        // loop through all possible starting rows and
        // columns
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // loop through all possible ending rows and
                // columns
                for (int rEnd = r; rEnd < m; rEnd++) {
                    for (int cEnd = c; cEnd < n; cEnd++) {
                        int submatrixSum
                            = 0; // initialize the sum of
                                 // the current submatrix to
                                 // 0
                        // loop through all elements of the
                        // current submatrix and add their
                        // values to the sum
                        for (int i = r; i <= rEnd; i++) {
                            for (int j = c; j <= cEnd;
                                 j++) {
                                submatrixSum += mat[i, j];
                            }
                        }
 
                        // if the sum of the submatrix is
                        // equal to k and its size is
                        // greater than the maximum size
                        // seen so far
                        if (submatrixSum == k
                            && (rEnd - r + 1)
                                       * (cEnd - c + 1)
                                   > maxSize) {
                            maxSubmatrix
                                .Clear(); // clear the
                                          // largest
                                          // submatrix List
                            // loop through all elements of
                            // the current submatrix and add
                            // them to the largest submatrix
                            // List
                            for (int i = r; i <= rEnd;
                                 i++) {
                                List<int> row
                                    = new List<int>();
                                for (int j = c; j <= cEnd;
                                     j++) {
                                    row.Add(mat[i, j]);
                                }
                                maxSubmatrix.Add(
                                    row); // add the row to
                                          // the largest
                                          // submatrix List
                            }
                            maxSize
                                = (rEnd - r + 1)
                                  * (cEnd - c
                                     + 1); // update the
                                           // maximum size
                                           // seen so far
                        }
                    }
                }
            }
        }
        return maxSubmatrix; // return the largest submatrix
                             // with the desired sum
    }
 
    public static void Main(string[] args)
    {
        int[, ] mat = { { 1, 7, -6, 5 },
                        { -8, 6, 7, -2 },
                        { 10, -15, 3, 2 },
                        { -5, 2, 0, 9 } };
        int k = 7;
        List<List<int> > largestSubmatrix
            = FindLargestSubmatrixWithSumK(mat, k);
        Console.WriteLine("Largest sub-matrix with sum " + k
                          + ":");
        foreach(List<int> row in largestSubmatrix)
        {
            foreach(int val in row)
            {
                Console.Write(val + " ");
            }
            Console.WriteLine();
        }
    }
}
// This code is contributed by user_dtewbxkn77n

Javascript

"use strict";
 
function findLargestSubmatrixWithSumK(mat, k) {
    let m = mat.length; // number of rows in the matrix
    let n = mat[0].length; // number of columns in the matrix
    let maxSubmatrix = []; // initialize the largest submatrix to an empty array
    let maxSize = 0; // initialize the maximum size to 0
     
    // loop through all possible starting rows and columns
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            // loop through all possible ending rows and columns
            for (let rEnd = r; rEnd < m; rEnd++) {
                for (let cEnd = c; cEnd < n; cEnd++) {
                    let submatrixSum = 0; // initialize the sum of the current submatrix to 0
                    // loop through all elements of the current submatrix and add their values to the sum
                    for (let i = r; i <= rEnd; i++) {
                        for (let j = c; j <= cEnd; j++) {
                            submatrixSum += mat[i][j];
                        }
                    }
                     
                    // if the sum of the submatrix is equal to k and its size is greater than the maximum size seen so far
                    if (submatrixSum === k && (rEnd - r + 1) * (cEnd - c + 1) > maxSize) {
                        maxSubmatrix = []; // clear the largest submatrix array
                        // loop through all elements of the current submatrix and add them to the largest submatrix array
                        for (let i = r; i <= rEnd; i++) {
                            let row = mat[i].slice(c, cEnd + 1); // get a subarray of the current row corresponding to the current submatrix column range
                            maxSubmatrix.push(row); // add the row to the largest submatrix array
                        }
                        maxSize = (rEnd - r + 1) * (cEnd - c + 1); // update the maximum size seen so far
                    }
                }
            }
        }
    }
    return maxSubmatrix; // return the largest submatrix with the desired sum
}
 
let mat = [[ 1, 7, -6, 5 ],
           [ -8, 6, 7, -2 ],
           [ 10, -15, 3, 2 ],
           [ -5, 2, 0, 9 ]];
let k = 7;
let largestSubmatrix = findLargestSubmatrixWithSumK(mat, k);
console.log("Largest sub-matrix with sum " + k + ":");
for (let row of largestSubmatrix) {
    console.log(row.join(" "));
}
 
// This code is contributed by akashish__

Output

Largest sub-matrix with sum 7:
7 -6 5 
6 7 -2 
-15 3 2

Complexity Analysis

Time Complexity:  O(n^4) . 
Auxiliary Space:O(n^2). .

Efficient Approach: 

Longest sub-array having sum k for 1-D array can be used to reduce the time complexity to O(n^3). The idea is to fix the left and right columns one by one and find the longest sub-array having sum equal to ‘k’ for contiguous rows for every left and right column pair. We basically find top and bottom row numbers (which are part of the largest sub-matrix) for every fixed left and right column pair. To find the top and bottom row numbers, calculate sum of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates sum of elements from left to right in row i. 

Now, apply Longest sub-array having sum k 1D algorithm on temp[], and get the longest sub-array having sum equal to ‘k’ of temp[]. This length would be the maximum possible length with left and right as boundary columns. Set the ‘top’ and ‘bottom’ row indexes for the left right column pair and calculate the area. In similar manner get the top, bottom, left, right indexes for other sub-matrices having sum equal to ‘k’ and print the one having maximum area. 

Implementation:

C++

// C++ implementation to find the largest area rectangular
// sub-matrix whose sum is equal to k
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 100;
 
// This function basically finds largest 'k'
// sum subarray in arr[0..n-1]. If 'k' sum
// doesn't exist, then it returns false. Else
// it returns true and sets starting and
// ending indexes as start and end.
bool sumEqualToK(int arr[], int& start,
                 int& end, int n, int k)
{
    // unordered_map 'um' implemented
    // as hash table
    unordered_map<int, int> um;
    int sum = 0, maxLen = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++) {
 
        // accumulate sum
        sum += arr[i];
 
        // when subarray starts from index '0'
        // update maxLength and start and end points
        if (sum == k) {
            maxLen = i + 1;
            start = 0;
            end = i;
        }
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        if (um.find(sum) == um.end())
            um[sum] = i;
 
        // check if 'sum-k' is present in 'um'
        // or not
        if (um.find(sum - k) != um.end()) {
 
            // update maxLength and start and end points
            if (maxLen < (i - um[sum - k])) {
                maxLen = i - um[sum - k];
                start = um[sum - k] + 1;
                end = i;
            }
        }
    }
 
    // Return true if maximum length is non-zero
    return (maxLen != 0);
}
 
// function to find the largest area rectangular
// sub-matrix whose sum is equal to k
void sumZeroMatrix(int mat[][MAX], int row, int col, int k)
{
    // Variables to store the temporary values
    int temp[row], area;
    bool sum;
    int up, down;
 
    // Variables to store the final output
    int fup = 0, fdown = 0, fleft = 0, fright = 0;
    int maxArea = INT_MIN;
 
    // Set the left column
    for (int left = 0; left < col; left++) {
        // Initialize all elements of temp as 0
        memset(temp, 0, sizeof(temp));
 
        // Set the right column for the left column
        // set by outer loop
        for (int right = left; right < col; right++) {
            // Calculate sum between current left
            // and right column for every row 'i'
            for (int i = 0; i < row; i++)
                temp[i] += mat[i][right];
 
            // Find largest subarray with 'k' sum in
            // temp[]. The sumEqualToK() function also
            // sets values of 'up' and 'down;'. So
            // if 'sum' is true then rectangle exists between
            // (up, left) and (down, right) which are the
            // boundary values.
            sum = sumEqualToK(temp, up, down, row, k);
            area = (down - up + 1) * (right - left + 1);
 
            // Compare no. of elements with previous
            // no. of elements in sub-Matrix.
            // If new sub-matrix has more elements
            // then update maxArea and final boundaries
            // like fup, fdown, fleft, fright
            if (sum && maxArea < area) {
                fup = up;
                fdown = down;
                fleft = left;
                fright = right;
                maxArea = area;
            }
        }
    }
 
    // If there is no change in boundaries
    // than check if mat[0][0] equals 'k'
    // If it is not equal to 'k' then print
    // that no such k-sum sub-matrix exists
    if (fup == 0 && fdown == 0 && fleft == 0 &&
        fright == 0 && mat[0][0] != k) {
        cout << "No sub-matrix with sum " << k << " exists";
        return;
    }
 
    // Print final values
 
    cout << "(Top, Left): "
         << "(" << fup << ", " << fleft
         << ")" << endl;
 
    cout << "(Bottom, Right): "
         << "(" << fdown << ", " << fright
         << ")" << endl;
 
    for (int j = fup; j <= fdown; j++) {
        for (int i = fleft; i <= fright; i++)
            cout << mat[j][i] << " ";
        cout << endl;
    }
}
 
// Driver program to test above
int main()
{
    int mat[][MAX] = { { 1, 7, -6, 5 },
                       { -8, 6, 7, -2 },
                       { 10, -15, 3, 2 },
                       { -5, 2, 0, 9 } };
 
    int row = 4, col = 4;
    int k = 7;
    sumZeroMatrix(mat, row, col, k);
    return 0;
}

Java

// Java implementation to find
// the largest area rectangular
// sub-matrix whose sum is equal to k
import java.util.*;
 
class GFG
{
 
static int MAX = 100;
static int start, end;
 
// This function basically finds largest 'k'
// sum subarray in arr[0..n-1]. If 'k' sum
// doesn't exist, then it returns false. Else
// it returns true and sets starting and
// ending indexes as start and end.
static boolean sumEqualToK(int arr[], int n, int k)
{
    // unordered_map 'um' implemented
    // as hash table
    HashMap<Integer,Integer> um =
    new HashMap<Integer,Integer>();
     
    int sum = 0, maxLen = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++)
    {
 
        // accumulate sum
        sum += arr[i];
 
        // when subarray starts from index '0'
        // update maxLength and start and end points
        if (sum == k)
        {
            maxLen = i + 1;
            start = 0;
            end = i;
        }
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        if (!um.containsKey(sum))
            um.put(sum, i);
 
        // check if 'sum-k' is present in 'um'
        // or not
        if (um.containsKey(sum - k))
        {
 
            // update maxLength and start and end points
            if (maxLen < (i - um.get(sum - k)))
            {
                maxLen = i - um.get(sum - k);
                start = um.get(sum - k) + 1;
                end = i;
            }
        }
    }
 
    // Return true if maximum length is non-zero
    return (maxLen != 0);
}
 
// function to find the largest area rectangular
// sub-matrix whose sum is equal to k
static void sumZeroMatrix(int mat[][], int row,
                            int col, int k)
{
    // Variables to store the temporary values
    int []temp = new int[row];
    int area;
    boolean sum = false;
 
    // Variables to store the final output
    int fup = 0, fdown = 0, fleft = 0, fright = 0;
    int maxArea = Integer.MIN_VALUE;
 
    // Set the left column
    for (int left = 0; left < col; left++)
    {
         
        // Initialize all elements of temp as 0
        temp = memset(temp, 0);
         
        // Set the right column for the left column
        // set by outer loop
        for (int right = left; right < col; right++)
        {
            // Calculate sum between current left
            // and right column for every row 'i'
            for (int i = 0; i < row; i++)
                temp[i] += mat[i][right];
 
            // Find largest subarray with 'k' sum in
            // temp[]. The sumEqualToK() function also
            // sets values of 'up' and 'down;'. So
            // if 'sum' is true then rectangle exists between
            // (up, left) and (down, right) which are the
            // boundary values.
            sum = sumEqualToK(temp, row, k);
            area = (end - start + 1) * (right - left + 1);
 
            // Compare no. of elements with previous
            // no. of elements in sub-Matrix.
            // If new sub-matrix has more elements
            // then update maxArea and final boundaries
            // like fup, fdown, fleft, fright
            if (sum && maxArea < area)
            {
                fup = start;
                fdown = end;
                fleft = left;
                fright = right;
                maxArea = area;
            }
        }
    }
 
    // If there is no change in boundaries
    // than check if mat[0][0] equals 'k'
    // If it is not equal to 'k' then print
    // that no such k-sum sub-matrix exists
    if (fup == 0 && fdown == 0 && fleft == 0 &&
        fright == 0 && mat[0][0] != k)
    {
        System.out.print("No sub-matrix with sum "
                        + k + " exists");
        return;
    }
 
    // Print final values
    System.out.print("(Top, Left): "
        + "(" + fup+ ", " + fleft
        + ")" +"\n");
 
    System.out.print("(Bottom, Right): "
        + "(" + fdown+ ", " + fright
        + ")" +"\n");
 
    for (int j = fup; j <= fdown; j++)
    {
        for (int i = fleft; i <= fright; i++)
            System.out.print(mat[j][i] + " ");
        System.out.println();
    }
}
static int[] memset(int []arr, int val)
{
    for(int i = 0; i < arr.length; i++)
        arr[i] = val;
    return arr;
}
 
// Driver code
public static void main(String[] args)
{
    int mat[][] = { { 1, 7, -6, 5 },
                    { -8, 6, 7, -2 },
                    { 10, -15, 3, 2 },
                    { -5, 2, 0, 9 } };
 
    int row = 4, col = 4;
    int k = 7;
    sumZeroMatrix(mat, row, col, k);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

import sys
 
class GFG :
    MAX = 100
    start = 0
    end = 0
     
    # This function basically finds largest 'k'
    # sum subarray in arr[0..n-1]. If 'k' sum
    # doesn't exist, then it returns false. Else
    # it returns true and sets starting and
    # ending indexes as start and end.
    @staticmethod
    def  sumEqualToK( arr,  n,  k) :
       
        # unordered_map 'um' implemented
        # as hash table
        um =  dict()
        sum = 0
        maxLen = 0
         
        # traverse the given array
        i = 0
        while (i < n) :
           
            # accumulate sum
            sum += arr[i]
             
            # when subarray starts from index '0'
            # update maxLength and start and end points
            if (sum == k) :
                maxLen = i + 1
                GFG.start = 0
                GFG.end = i
                 
            # make an entry for 'sum' if it is
            # not present in 'um'
            if (not (sum in um.keys())) :
                um[sum] = i
                 
            # check if 'sum-k' is present in 'um'
            # or not
            if ((sum - k in um.keys())) :
               
                # update maxLength and start and end points
                if (maxLen < (i - um.get(sum - k))) :
                    maxLen = i - um.get(sum - k)
                    GFG.start = um.get(sum - k) + 1
                    GFG.end = i
            i += 1
             
        # Return true if maximum length is non-zero
        return (maxLen != 0)
       
    # function to find the largest area rectangular
    # sub-matrix whose sum is equal to k
    @staticmethod
    def sumZeroMatrix( mat,  row,  col,  k) :
       
        # Variables to store the temporary values
        temp = [0] * (row)
        area = 0
        sum = False
         
        # Variables to store the final output
        fup = 0
        fdown = 0
        fleft = 0
        fright = 0
        maxArea = -sys.maxsize
         
        # Set the left column
        left = 0
        while (left < col) :
           
            # Initialize all elements of temp as 0
            temp = GFG.memset(temp, 0)
             
            # Set the right column for the left column
            # set by outer loop
            right = left
            while (right < col) :
               
                # Calculate sum between current left
                # and right column for every row 'i'
                i = 0
                while (i < row) :
                    temp[i] += mat[i][right]
                    i += 1
                     
                # Find largest subarray with 'k' sum in
                # temp[]. The sumEqualToK() function also
                # sets values of 'up' and 'down;'. So
                # if 'sum' is true then rectangle exists between
                # (up, left) and (down, right) which are the
                # boundary values.
                sum = GFG.sumEqualToK(temp, row, k)
                area = (GFG.end - GFG.start + 1) * (right - left + 1)
                 
                # Compare no. of elements with previous
                # no. of elements in sub-Matrix.
                # If new sub-matrix has more elements
                # then update maxArea and final boundaries
                # like fup, fdown, fleft, fright
                if (sum and maxArea < area) :
                    fup = GFG.start
                    fdown = GFG.end
                    fleft = left
                    fright = right
                    maxArea = area
                right += 1
            left += 1
             
        # If there is no change in boundaries
        # than check if mat[0][0] equals 'k'
        # If it is not equal to 'k' then print
        # that no such k-sum sub-matrix exists
        if (fup == 0 and fdown == 0 and fleft == 0 and fright == 0 and mat[0][0] != k) :
            print("No sub-matrix with sum " + str(k) + " exists", end ="")
            return
        # Print final values
        print("(Top, Left): " + "(" + str(fup) + ", " + str(fleft) + ")" + "\n", end ="")
        print("(Bottom, Right): " + "(" + str(fdown) + ", " + str(fright) + ")" + "\n", end ="")
        j = fup
        while (j <= fdown) :
            i = fleft
            while (i <= fright) :
                print(str(mat[j][i]) + " ", end ="")
                i += 1
            print()
            j += 1
    @staticmethod
    def  memset( arr,  val) :
        i = 0
        while (i < len(arr)) :
            arr[i] = val
            i += 1
        return arr
       
    # Driver code
    @staticmethod
    def main( args) :
        mat = [[1, 7, -6, 5], [-8, 6, 7, -2], [10, -15, 3, 2], [-5, 2, 0, 9]]
        row = 4
        col = 4
        k = 7
        GFG.sumZeroMatrix(mat, row, col, k)
     
if __name__=="__main__":
    GFG.main([])
     
    # This code is contributed by aadityaburujwale.

C#

// C# implementation to find
// the largest area rectangular
// sub-matrix whose sum is equal to k
using System;
using System.Collections.Generic;
 
class GFG
{
 
static int MAX = 100;
static int start, end;
 
// This function basically finds largest 'k'
// sum subarray in arr[0..n-1]. If 'k' sum
// doesn't exist, then it returns false. Else
// it returns true and sets starting and
// ending indexes as start and end.
static bool sumEqualToK(int []arr, int n, int k)
{
    // unordered_map 'um' implemented
    // as hash table
    Dictionary<int,int> um =
    new Dictionary<int,int>();
     
    int sum = 0, maxLen = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++)
    {
 
        // accumulate sum
        sum += arr[i];
 
        // when subarray starts from index '0'
        // update maxLength and start and end points
        if (sum == k)
        {
            maxLen = i + 1;
            start = 0;
            end = i;
        }
 
        // make an entry for 'sum' if it is
        // not present in 'um'
        if (!um.ContainsKey(sum))
            um.Add(sum, i);
 
        // check if 'sum-k' is present in 'um'
        // or not
        if (um.ContainsKey(sum - k))
        {
 
            // update maxLength and start and end points
            if (maxLen < (i - um[sum - k]))
            {
                maxLen = i - um[sum - k];
                start = um[sum - k] + 1;
                end = i;
            }
        }
    }
 
    // Return true if maximum length is non-zero
    return (maxLen != 0);
}
 
// function to find the largest area rectangular
// sub-matrix whose sum is equal to k
static void sumZeroMatrix(int [,]mat, int row,
                            int col, int k)
{
    // Variables to store the temporary values
    int []temp = new int[row];
    int area;
    bool sum = false;
 
    // Variables to store the readonly output
    int fup = 0, fdown = 0, fleft = 0, fright = 0;
    int maxArea = int.MinValue;
 
    // Set the left column
    for (int left = 0; left < col; left++)
    {
         
        // Initialize all elements of temp as 0
        temp = memset(temp, 0);
         
        // Set the right column for the left column
        // set by outer loop
        for (int right = left; right < col; right++)
        {
            // Calculate sum between current left
            // and right column for every row 'i'
            for (int i = 0; i < row; i++)
                temp[i] += mat[i, right];
 
            // Find largest subarray with 'k' sum in
            // []temp. The sumEqualToK() function also
            // sets values of 'up' and 'down;'. So
            // if 'sum' is true then rectangle exists between
            // (up, left) and (down, right) which are the
            // boundary values.
            sum = sumEqualToK(temp, row, k);
            area = (end - start + 1) * (right - left + 1);
 
            // Compare no. of elements with previous
            // no. of elements in sub-Matrix.
            // If new sub-matrix has more elements
            // then update maxArea and readonly boundaries
            // like fup, fdown, fleft, fright
            if (sum && maxArea < area)
            {
                fup = start;
                fdown = end;
                fleft = left;
                fright = right;
                maxArea = area;
            }
        }
    }
 
    // If there is no change in boundaries
    // than check if mat[0,0] equals 'k'
    // If it is not equal to 'k' then print
    // that no such k-sum sub-matrix exists
    if (fup == 0 && fdown == 0 && fleft == 0 &&
        fright == 0 && mat[0, 0] != k)
    {
        Console.Write("No sub-matrix with sum "
                        + k + " exists");
        return;
    }
 
    // Print readonly values
    Console.Write("(Top, Left): "
        + "(" + fup+ ", " + fleft
        + ")" +"\n");
 
    Console.Write("(Bottom, Right): "
        + "(" + fdown+ ", " + fright
        + ")" +"\n");
 
    for (int j = fup; j <= fdown; j++)
    {
        for (int i = fleft; i <= fright; i++)
            Console.Write(mat[j, i] + " ");
        Console.WriteLine();
    }
}
static int[] memset(int []arr, int val)
{
    for(int i = 0; i < arr.Length; i++)
        arr[i] = val;
    return arr;
}
 
// Driver code
public static void Main(String[] args)
{
    int [,]mat = { { 1, 7, -6, 5 },
                    { -8, 6, 7, -2 },
                    { 10, -15, 3, 2 },
                    { -5, 2, 0, 9 } };
 
    int row = 4, col = 4;
    int k = 7;
    sumZeroMatrix(mat, row, col, k);
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

// JavaScript implementation to find
// the largest area rectangular
// sub-matrix whose sum is equal to k
var MAX = 100;
var start;
var end;
 
// This function basically finds largest 'k'
// sum subarray in arr[0..n-1]. If 'k' sum
// doesn't exist, then it returns false. Else
// it returns true and sets starting and
// ending indexes as start and end.
function sumEqualToK(arr, n, k){
    // unordered_map 'um' implemented
    // as hash table
    var um = new Map();
     
    var sum = 0, maxLen = 0;
     
    // traverse the given array
    for(let i=0;i<n;i++){
         
        // accumulate sum
        sum += arr[i];
         
        // when subarray starts from index '0'
        // update maxLength and start and end points
        if(sum==k){
            maxLen = i+1;
            start = 0;
            end = i;
        }
         
        // make an entry for 'sum' if it is
        // not present in 'um'
        if(!um.has(sum)){
            um.set(sum, i);
        }
         
        // check if 'sum-k' is present in 'um'
        // or not
        if(um.has(sum-k)){
            // update maxLength and start and end points
            if(maxLen < (i - um.get(sum - k))){
                maxLen = i-um.get(sum-k);
                start = um.get(sum-k) + 1;
                end = i;
            }
        }
    }
     
    // Return true if maximum length is non-zero
    return (maxLen!=0);
}
 
// function to find the largest area rectangular
// sub-matrix whose sum is equal to k
function sumZeroMatrix(mat, row, col, k){
    var temp = new Array(row);
    var area;
    var sum = false;
     
    // Variables to store the final output
    var fup = 0, fdown = 0, fleft = 0, fright = 0;
    var maxArea = Number.MIN_VALUE;
     
    // Set the left column
    for (let left = 0; left < col; left++)
    {
        // Initialize all elements of temp as 0
        temp = memset(temp, 0);
 
        // Set the right column for the left column
        // set by outer loop
        for (let right = left; right < col; right++)
        {
            // Calculate sum between current left
            // and right column for every row 'i'
            for (let i = 0; i < row; i++){
                temp[i] += mat[i][right];
            }
             
            // Find largest subarray with 'k' sum in
            // temp[]. The sumEqualToK() function also
            // sets values of 'up' and 'down;'. So
            // if 'sum' is true then rectangle exists between
            // (up, left) and (down, right) which are the
            // boundary values.
            sum = sumEqualToK(temp, row, k);
            area = (end - start + 1) * (right - left + 1);
 
            // Compare no. of elements with previous
            // no. of elements in sub-Matrix.
            // If new sub-matrix has more elements
            // then update maxArea and final boundaries
            // like fup, fdown, fleft, fright
            if (sum && maxArea < area)
            {
                fup = start;
                fdown = end;
                fleft = left;
                fright = right;
                maxArea = area;
            }
        }
    }
     
    // If there is no change in boundaries
    // than check if mat[0][0] equals 'k'
    // If it is not equal to 'k' then print
    // that no such k-sum sub-matrix exists
    if (fup == 0 && fdown == 0 && fleft == 0 &&
        fright == 0 && mat[0][0] != k)
    {
        console.log("No sub-matrix with sum "
                        + k + " exists");
        return;
    }
     
    // Print final values
    console.log("(Top, Left): "
        + "(" + fup+ ", " + fleft
        + ")" +"<br>");
 
    console.log("(Bottom, Right): "
        + "(" + fdown+ ", " + fright
        + ")" +"<br>");
 
    for (let j = fup; j <= fdown; j++)
    {
        for (let i = fleft; i <= fright; i++)
        {
            console.log(mat[j][i] + " ");
        }
        console.log("<br>");
    }
}
 
function memset(arr, val){
    for(let i = 0; i < arr.length; i++){
        arr[i] = val;
    }
    return arr;
}
 
var mat = [[1, 7, -6, 5],
           [-8, 6, 7, -2],
           [10, -15, 3, 2],
           [-5, 2, 0, 9]];
 
var row = 4, col = 4;
var k = 7;
 
sumZeroMatrix(mat, row, col, k);
 
// This code is contributed by lokeshmvs21.

Output

(Top, Left): (0, 1)
(Bottom, Right): (2, 3)
7 -6 5 
6 7 -2 
-15 3 2

Complexity Analysis

  • Time Complexity: O(n^3). 
  • Auxiliary Space: O(n).

 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Sort a nearly sorted array using STL Sort a nearly sorted array using STL
Best Time to Buy and Sell Stock VI (with transaction fee) Best Time to Buy and Sell Stock VI (with transaction fee)
Print the last occurrence of elements in array in relative order Print the last occurrence of elements in array in relative order
Subarray whose absolute sum is closest to K Subarray whose absolute sum is closest to K
Split array to three subarrays such that sum of first and third subarray is equal and maximum Split array to three subarrays such that sum of first and third subarray is equal and maximum

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 8



 

Horje