Given a 2D array, find the minimum sum submatrix in it.
Examples:
Input : M[][] = {{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}}
Output : -26
Submatrix starting from (Top, Left): (0, 0)
and ending at (Bottom, Right): (1, 4) indexes.
The elements are of the submatrix are:
{ {1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1} } having sum = -26
Method 1 (Naive Approach): Check every possible submatrix in a given 2D array. This solution requires 4 nested loops and the time complexity of this solution would be O(n^4).
Method 2 (Efficient Approach):
Kadane’s algorithm for the 1D 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 minimum sum contiguous rows for every left and right column pair. We basically find top and bottom row numbers (which have minimum sum) for every fixed left and right column pair. To find the top and bottom row numbers, calculate the sum of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates the sum of elements from left to right in row i.
If we apply Kadane’s 1D algorithm on temp[] and get the minimum sum subarray of temp, this minimum sum would be the minimum possible sum with left and right as boundary columns. To get the overall minimum sum, we compare this sum with the minimum sum so far.
Implementation:
C++
// C++ implementation to find minimum sum // submatrix in a given 2D array#include <bits/stdc++.h>using namespace std;#define ROW 4#define COL 5// Implementation of Kadane's algorithm for // 1D array. The function returns the minimum // sum and stores starting and ending indexes// of the minimum sum subarray at addresses// pointed by start and finish pointers// respectively.int kadane(int* arr, int* start, int* finish, int n){ // initialize sum, maxSum and int sum = 0, minSum = INT_MAX, i; // Just some initial value to check for // all negative values case *finish = -1; // local variable int local_start = 0; for (i = 0; i < n; ++i) { sum += arr[i]; if (sum > 0) { sum = 0; local_start = i + 1; } else if (sum < minSum) { minSum = sum; *start = local_start; *finish = i; } } // There is at-least one non-negative number if (*finish != -1) return minSum; // Special Case: When all numbers in arr[] // are positive minSum = arr[0]; *start = *finish = 0; // Find the minimum element in array for (i = 1; i < n; i++) { if (arr[i] < minSum) { minSum = arr[i]; *start = *finish = i; } } return minSum;}// function to find minimum sum submatrix// in a given 2D arrayvoid findMinSumSubmatrix(int M[][COL]){ // Variables to store the final output int minSum = INT_MAX, finalLeft, finalRight, finalTop, finalBottom; int left, right, i; int temp[ROW], sum, start, finish; // Set the left column for (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 (right = left; right < COL; ++right) { // Calculate sum between current left // and right for every row 'i' for (i = 0; i < ROW; ++i) temp[i] += M[i][right]; // Find the minimum sum subarray in temp[]. // The kadane() function also sets values // of start and finish. So 'sum' is sum of // rectangle between (start, left) and // (finish, right) which is the minimum sum // with boundary columns strictly as // left and right. sum = kadane(temp, &start, &finish, ROW); // Compare sum with maximum sum so far. If // sum is more, then update maxSum and other // output values if (sum < minSum) { minSum = sum; finalLeft = left; finalRight = right; finalTop = start; finalBottom = finish; } } } // Print final values cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n"; cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n"; cout << "Minimum sum: " << minSum;}// Driver program to test aboveint main(){ int M[ROW][COL] = { { 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 }, { 3, 8, 10, 1, 3 }, { -4, -1, 1, 7, -6 } }; findMinSumSubmatrix(M); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { static int ROW = 4; static int COL = 5; static int start; static int finish; static int kadane(int[] arr, int n) { // initialize sum, maxSum and int sum = 0, minSum = Integer.MAX_VALUE, i; // Just some initial value to check for // all negative values case finish = -1; // local variable int local_start = 0; for (i = 0; i < n; ++i) { sum += arr[i]; if (sum > 0) { sum = 0; local_start = i + 1; } else if (sum < minSum) { minSum = sum; start = local_start; finish = i; } } // There is at-least one non-negative number if (finish != -1) return minSum; // Special Case: When all numbers in arr[] // are positive minSum = arr[0]; start = finish = 0; // Find the minimum element in array for (i = 1; i < n; i++) { if (arr[i] < minSum) { minSum = arr[i]; start = finish = i; } } return minSum; } // function to find minimum sum submatrix // in a given 2D array static void findMinSumSubmatrix(int[][] M) { // Variables to store the final output int minSum = Integer.MAX_VALUE; int finalLeft = 0 , finalRight = 0, finalTop = 0, finalBottom = 0; int left, right, i; int []temp= new int[ROW]; int sum; // Set the left column for (left = 0; left < COL; ++left) { // Initialize all elements of temp as 0 Arrays.fill(temp, 0); // Set the right column for the left // column set by outer loop for (right = left; right < COL; ++right) { // Calculate sum between current left // and right for every row 'i' for (i = 0; i < ROW; ++i) temp[i] += M[i][right]; // Find the minimum sum subarray in temp[]. // The kadane() function also sets values // of start and finish. So 'sum' is sum of // rectangle between (start, left) and // (finish, right) which is the minimum sum // with boundary columns strictly as // left and right. sum = kadane(temp, ROW); // Compare sum with maximum sum so far. If // sum is more, then update maxSum and other // output values if (sum < minSum) { minSum = sum; finalLeft = left; finalRight = right; finalTop = start; finalBottom = finish; } } } // Print final values System.out.println("(Top, Left): (" + finalTop + ", " + finalLeft + ")"); System.out.println("(Bottom, Right): (" + finalBottom + ", " + finalRight + ")"); System.out.println("Minimum sum: "+ minSum); } // Driver program to test above public static void main (String[] args) { int[][] M ={{ 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 }, { 3, 8, 10, 1, 3 }, { -4, -1, 1, 7, -6 }}; findMinSumSubmatrix(M); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation to find minimum # sum submatrix in a given 2D arrayimport sys# Implementation of Kadane's algorithm for# 1D array. The function returns the minimum# sum and stores starting and ending indexes# of the minimum sum subarray at addresses# pointed by start and finish pointers# respectively.def kadane(arr, start, finish, n): # Initialize sum, maxSum and sum, minSum = 0, sys.maxsize # Just some initial value to check # for all negative values case finish = -1 # Local variable local_start = 0 for i in range(n): sum += arr[i] if (sum > 0): sum = 0 local_start = i + 1 elif (sum < minSum): minSum = sum start = local_start finish = i # There is at-least one non-negative number if (finish != -1): return minSum, start, finish # Special Case: When all numbers in arr[] # are positive minSum = arr[0] start, finish = 0, 0 # Find the minimum element in array for i in range(1, n): if (arr[i] < minSum): minSum = arr[i] start = finish = i return minSum, start, finish# Function to find minimum sum submatrix# in a given 2D arraydef findMinSumSubmatrix(M): # Variables to store the final output minSum = sys.maxsize finalLeft = 0 finalRight = 0 finalTop = 0 finalBottom = 0 #left, right, i = 0, 0, 0 sum, start, finish = 0, 0, 0 # Set the left column for left in range(5): # Initialize all elements of temp as 0 temp = [0 for i in range(5)] # Set the right column for the left # column set by outer loop for right in range(left, 5): # Calculate sum between current left # and right for every row 'i' for i in range(4): temp[i] += M[i][right] # Find the minimum sum subarray in temp[]. # The kadane() function also sets values # of start and finish. So 'sum' is sum of # rectangle between (start, left) and # (finish, right) which is the minimum sum # with boundary columns strictly as # left and right. sum, start, finish = kadane(temp, start, finish, 4) # Compare sum with maximum sum so far. If # sum is more, then update maxSum and other # output values if (sum < minSum): minSum = sum finalLeft = left finalRight = right finalTop = start finalBottom = finish # Print final values print("(Top, Left): (", finalTop, ",", finalLeft, ")") print("(Bottom, Right): (", finalBottom, ",", finalRight, ")") print("Minimum sum:", minSum)# Driver codeif __name__ == '__main__': M = [ [ 1, 2, -1, -4, -20 ], [ -8, -3, 4, 2, 1 ], [ 3, 8, 10, 1, 3 ], [ -4, -1, 1, 7, -6 ] ] findMinSumSubmatrix(M)# This code is contributed by mohit kumar 29 |
C#
using System;public class GFG{ static int ROW = 4; static int COL = 5; static int start; static int finish; static int kadane(int[] arr, int n) { // initialize sum, maxSum and int sum = 0, minSum = Int32.MaxValue, i; // Just some initial value to check for // all negative values case finish = -1; // local variable int local_start = 0; for (i = 0; i < n; ++i) { sum += arr[i]; if (sum > 0) { sum = 0; local_start = i + 1; } else if (sum < minSum) { minSum = sum; start = local_start; finish = i; } } // There is at-least one non-negative number if (finish != -1) return minSum; // Special Case: When all numbers in arr[] // are positive minSum = arr[0]; start = finish = 0; // Find the minimum element in array for (i = 1; i < n; i++) { if (arr[i] < minSum) { minSum = arr[i]; start = finish = i; } } return minSum; } // function to find minimum sum submatrix // in a given 2D array static void findMinSumSubmatrix(int[,] M) { // Variables to store the final output int minSum = Int32.MaxValue; int finalLeft = 0 , finalRight = 0, finalTop = 0, finalBottom = 0; int left, right, i; int []temp= new int[ROW]; int sum; // Set the left column for (left = 0; left < COL; ++left) { // Initialize all elements of temp as 0 Array.Fill(temp, 0); // Set the right column for the left // column set by outer loop for (right = left; right < COL; ++right) { // Calculate sum between current left // and right for every row 'i' for (i = 0; i < ROW; ++i) temp[i] += M[i, right]; // Find the minimum sum subarray in temp[]. // The kadane() function also sets values // of start and finish. So 'sum' is sum of // rectangle between (start, left) and // (finish, right) which is the minimum sum // with boundary columns strictly as // left and right. sum = kadane(temp, ROW); // Compare sum with maximum sum so far. If // sum is more, then update maxSum and other // output values if (sum < minSum) { minSum = sum; finalLeft = left; finalRight = right; finalTop = start; finalBottom = finish; } } } Console.WriteLine("(Top, Left): (" + finalTop + ", " + finalLeft + ")"); Console.WriteLine("(Bottom, Right): (" + finalBottom + ", " + finalRight + ")"); Console.WriteLine("Minimum sum: "+ minSum); } // Driver program to test above static public void Main () { int[,] M ={{ 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 }, { 3, 8, 10, 1, 3 }, { -4, -1, 1, 7, -6 }}; findMinSumSubmatrix(M); }}// This code is contributed by rag2127 |
Javascript
<script>/*package whatever //do not writepackage name here */ var ROW = 4; var COL = 5; var start; var finish; function kadane(arr , n) { // initialize sum, maxSum and var sum = 0, minSum = Number.MAX_VALUE, i; // Just some initial value to check for // all negative values case finish = -1; // local variable var local_start = 0; for (i = 0; i < n; ++i) { sum += arr[i]; if (sum > 0) { sum = 0; local_start = i + 1; } else if (sum < minSum) { minSum = sum; start = local_start; finish = i; } } // There is at-least one non-negative number if (finish != -1) return minSum; // Special Case: When all numbers in arr // are positive minSum = arr[0]; start = finish = 0; // Find the minimum element in array for (i = 1; i < n; i++) { if (arr[i] < minSum) { minSum = arr[i]; start = finish = i; } } return minSum; } // function to find minimum sum submatrix // in a given 2D array function findMinSumSubmatrix(M) { // Variables to store the final output var minSum = Number.MAX_VALUE; var finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0; var left, right, i; var temp = Array(ROW).fill(0); var sum; // Set the left column for (left = 0; left < COL; ++left) { // Initialize all elements of temp as 0 temp.fill(0); // Set the right column for the left // column set by outer loop for (right = left; right < COL; ++right) { // Calculate sum between current left // and right for every row 'i' for (i = 0; i < ROW; ++i) temp[i] += M[i][right]; // Find the minimum sum subarray in temp. // The kadane() function also sets values // of start and finish. So 'sum' is sum of // rectangle between (start, left) and // (finish, right) which is the minimum sum // with boundary columns strictly as // left and right. sum = kadane(temp, ROW); // Compare sum with maximum sum so far. If // sum is more, then update maxSum and other // output values if (sum < minSum) { minSum = sum; finalLeft = left; finalRight = right; finalTop = start; finalBottom = finish; } } } // Print final values document.write("(Top, Left): (" + finalTop + ", " + finalLeft + ")<br/>"); document.write("(Bottom, Right): (" + finalBottom + ", " + finalRight + ")<br/>"); document.write("Minimum sum: " + minSum); } // Driver program to test above var M = [ [ 1, 2, -1, -4, -20 ], [ -8, -3, 4, 2, 1 ], [ 3, 8, 10, 1, 3 ], [ -4, -1, 1, 7, -6 ] ]; findMinSumSubmatrix(M);// This code contributed by umadevi9616</script> |
Output
(Top, Left): (0, 0) (Bottom, Right): (1, 4) Minimum sum: -26
Time Complexity: O(n3)
Auxiliary Space: O(ROW)
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
