# 363-max-sum-of-rectangle-no-larger-than-k

## Question

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/description/

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:

``````Given matrix = [
[1,  0, 1],
[0, -2, 3]
]
k = 2
``````

The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

## Thought Process

1. Presum and Binary Search
1. We need a way to get all the rectangles, which can be define by 4 variables r1, r2, c1 c2 that means the top row, bottom row, left column and right column
2. Unlike brute force that requires time complexity O(m^2n^2), we can use built-in TreeSet to find the ceilling of (currentSum - k)
3. Adding partial sum ending at column and r2, we can do binary search on
4. Time complexity O(m^2nlogn)
5. Space complexity O(n)

## Solution

``````class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix.length;
int res = Integer.MIN_VALUE;
for (int r1 = 0; r1 < m; r1++) {
int[] presum = new int[n];
for (int r2 = r1; r2 < m; r2++) {
TreeSet<Integer> set = new TreeSet<Integer>();
int val = 0;
for (int c = 0; c < n; c++) {
presum[c] += matrix[r2][c];
val += presum[c];
Integer prev = set.ceiling(val - k);
if (prev != null) {
res = Math.max(res, val - prev);
}
}
}
}
return res;
}
}
``````
``````class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix.length;
int res = Integer.MIN_VALUE;
for (int c1 = 0; c1 < n; c1++) {
int[] presum = new int[m];
for (int c2 = c1; c2 < n; c2++) {
TreeSet<Integer> set = new TreeSet<Integer>();
int val = 0;
for (int r = 0; r < m; r++) {
presum[r] += matrix[r][c2];
val += presum[r];
Integer prev = set.ceiling(val - k);
if (prev != null) {
res = Math.max(res, val - prev);
}