# 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