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 approachimport 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 usagemat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]k = 12largestSubmatrix = 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 kvoid 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 aboveint 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 kimport 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 kstatic 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 codepublic 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 sysclass 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 kusing 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 kstatic 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 codepublic 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 kvar 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 kfunction 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).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
