Home » Technical Interview Questions » Dynamic Programming Interview Questions » Maximum sum rectangle in a 2D matrix

Maximum sum rectangle in a 2D matrix


Reading Time - 4 mins


Difficulty Level Medium

Problem Statement

Find the maximum sum rectangle in a 2D matrix i.e. to find a sub-matrix with maximum sum. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and find the maximum value.

Example

Maximum sum rectangle in a 2D matrix

{ 0      10      0
 -1       0    100
 10    -100     10 }
110

Explanation: Here, in this given input we have two possible answers. Like if we choose a sub-matrix of size 2×2 from first row first column to second-row third column. And we can also select a sub-matrix of size 2×1 from the second-row third column to the third row, third column. Both of the results will give the same sum 110 as the answer.

{ 100
  -10
  100 }
190

Explanation: Here, in this given input 2D array. We can choose the whole matrix as a result because that will provide us with a total of 190.

Approach for finding maximum sum rectangle in a 2D matrix

Naive Solution

We can find the maximum sum submatrix in given matrix by using a naive solution. We can use four nested loops each for different indices. So, one will be for starting row index, starting column index, ending row index, and ending column index. We can use a 2D prefix array for storing the sum of prefixes. This approach can optimize our naive approach a bit but that will not efficient enough though.

READ  Divisible Pairs Counting

Efficient Solution

So, instead of using a naive solution, we will use Kadane’s algorithm for solving this problem efficiently. But the problem is now, how can we apply Kadane’s algorithm in a 2D matrix? We will promptly fix two columns, one for the left column and one for the right column. Then we store the sum between two columns in an array and then use Kadane’s algorithm for finding the maximum continuous sum of rows between those columns. We update our answer with the maximum value. After doing this for all possible combinations, we have our maximum sum rectangle in a 2D matrix.

Code to find the maximum sum rectangle in a 2D matrix

C++ Code

#include<bits/stdc++.h>
using namespace std;

int findMaximumSubMatrix(vector<vector<int>> matrix, int n, int m){
    // stores the prefixSum of rows
    vector<vector<int>> prefixSum(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            prefixSum[i][j] = matrix[i][j];
    }

    // calculation prefix sum for each row
    for(int i=0;i<n;i++){
        for(int j=1;j<m;j++)
            prefixSum[i][j] += prefixSum[i][j-1];
    }

    // store indices of submatrix with maximum sum
    int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
    int maxSum = INT_MIN;
    
    // use Kadane's algorithm for finding maximum contiguous sum in 1D array
    for(int firstCol=0;firstCol<m;firstCol++){
        for(int secondCol=firstCol;secondCol<m;secondCol++){
            int tmp[n]; // stores the sum between two columns for each row
            for(int row=0;row<n;row++)
                tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);

            int curSum = 0, curMaxSum = 0;
            int curStartRow = 0, tmpStartRow = 0, curEndRow = -1;
            
            for(int curRow=0;curRow<n;curRow++){
                curSum += tmp[curRow];
                if(curSum < 0) {
                    curSum = 0;
                    tmpStartRow = curRow+1;
                } else if(curSum > curMaxSum) {
                    curMaxSum = curSum;
                    curStartRow = tmpStartRow;
                    curEndRow = curRow;
                }
            }

            if(curEndRow == -1) {
                curMaxSum = tmp[0];
                curStartRow = 0;
                curEndRow = 0;
                for(int i=1;i<n;i++){
                    if(tmp[i] > curMaxSum){
                        curMaxSum = tmp[0];
                        curStartRow = i;
                        curEndRow = i;
                    }
                }
            }

            if(curMaxSum > maxSum){
                maxSum = curMaxSum;
                startCol = firstCol;
                endCol = secondCol;
                startRow = curStartRow;
                endRow = curEndRow;
            }
        }
    }
    cout<<"Sub-matrix with max Sum"<<endl;
    for(int i=startRow;i<=endRow;i++){
        for(int j=startCol;j<=endCol;j++){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    return maxSum;
}

int main(){
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        vector<vector<int>> matrix(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                cin>>matrix[i][j];
        }
        int ans = findMaximumSubMatrix(matrix, n, m);
        cout<<ans<<endl;
    }
}
2
3 3
1 2 3 4 5 6 7 8 -100
2 4
102 1545 87 989 -8989 -45 120 -855
Sub-matrix with max Sum
1 2 
4 5 
7 8 
27
Sub-matrix with max Sum
102 1545 87 989 
2723

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int findMaximumSubMatrix(int[][] matrix, int n, int m){
        // stores the prefixSum of rows
        int[][] prefixSum = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                prefixSum[i][j] = matrix[i][j];
        }
    
        // calculation prefix sum for each row
        for(int i=0;i<n;i++){
            for(int j=1;j<m;j++)
                prefixSum[i][j] += prefixSum[i][j-1];
        }
    
        int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
        int maxSum = Integer.MIN_VALUE;;
        for(int firstCol=0;firstCol<m;firstCol++){
            for(int secondCol=firstCol;secondCol<m;secondCol++){
                int tmp[] = new int[n]; // stores the sum between two columns for each row
                for(int row=0;row<n;row++)
                    tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
    
                int curSum = 0, curMaxSum = 0;
                int curStartRow = 0, tmpStartRow = 0, curEndRow = -1;
                for(int curRow=0;curRow<n;curRow++){
                    curSum += tmp[curRow];
                    if(curSum < 0) {
                        curSum = 0;
                        tmpStartRow = curRow+1;
                    } else if(curSum > curMaxSum) {
                        curMaxSum = curSum;
                        curStartRow = tmpStartRow;
                        curEndRow = curRow;
                    }
                }
    
                if(curEndRow == -1) {
                    curMaxSum = tmp[0];
                    curStartRow = 0;
                    curEndRow = 0;
                    for(int i=1;i<n;i++){
                        if(tmp[i] > curMaxSum){
                            curMaxSum = tmp[0];
                            curStartRow = i;
                            curEndRow = i;
                        }
                    }
                }
    
                if(curMaxSum > maxSum){
                    maxSum = curMaxSum;
                    startCol = firstCol;
                    endCol = secondCol;
                    startRow = curStartRow;
                    endRow = curEndRow;
                }
            }
        }
        
        System.out.println("Sub-matrix with max Sum");
        for(int i=startRow;i<=endRow;i++){
            for(int j=startCol;j<=endCol;j++){
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
        return maxSum;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int matrix[][] = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++)
                    matrix[i][j] = sc.nextInt();
            }
            int ans = findMaximumSubMatrix(matrix, n, m);
            System.out.println(ans);
        }
    }
}
2
3 3
1 2 3 4 5 6 7 8 -100
2 4
102 1545 87 989 -8989 -45 120 -855
Sub-matrix with max Sum 
1 2
4 5 
7 8 
27 
Sub-matrix with max Sum 
102 1545 87 989 
2723

Complexity Analysis

Time Complexity: O(N^3)

The maximum sum rectangle in a 2D matrix problem has a polynomial-time complexity of O(N^3) because there are three nested loops. Two for fixing columns and one for Kadane’s Algorithm.

READ  Friends Pairing Problem

Space Complexity: O(N^2)

Since we made a 2D prefix Sum array. We have space complexity of O(N^2).

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions