Max Sum of Rectangle No Larger Than K

This page explains Java solution to problem Max Sum of Rectangle No Larger Than K using Map data structure.

Problem Statement

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example 1:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation:
Because the sum of rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class MaxSumOfRectangleNoLargerThanK {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if(matrix == null || matrix.length == 0) return 0;

        int m = matrix.length;
        int n = matrix[0].length;

        int res = Integer.MIN_VALUE;
        for(int fromCol = 0; fromCol < n; fromCol++) {
            int[] colSum = new int[m];
            for(int toCol = fromCol; toCol < n; toCol++){
                for(int row = 0; row < m; row++) {
                    colSum[row] += matrix[row][toCol];
                }

                //Kadane's Algorithm to calculate max sum
                int maxSum = kadane(colSum);

                //If it is exactly K we have our answer
                if(maxSum == k) return k;

                //Assign MaxValue if it is less than k
                else if(maxSum < k) res = Math.max(res, maxSum);

                //Else if it is greater than k,
                else {
                    maxSum = maxSumLessThanK(colSum, k);
                    if(maxSum == k) return k;
                    else res = Math.max(res, maxSum);
                }
            }
        }

        return res;
    }

    private int kadane(int[] arr) {
        int maxSum = arr[0], currentSum = arr[0];
        for(int i = 1; i < arr.length; i++) {
            int num = arr[i];
            currentSum = Math.max(currentSum + num, num);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    private int maxSumLessThanK(int[] arr, int k) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(0);
        int currentSum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < arr.length; i++) {
            currentSum += arr[i];
            Integer findNum = set.ceiling(currentSum - k);
            if(findNum != null) maxSum = Math.max(maxSum, currentSum - findNum);
            set.add(currentSum);
        }
        return maxSum;
    }
}

Time Complexity

O(N2 * (M + N log N)) Where
M is total number of rows in an input array
N is total number of cols in an input array

Space Complexity

O(M + N) Where
M is total number of rows in an input array
N is total number of cols in an input array