# 2 Accepted Java Solution

• Decide to post because I was actually asked this question during my interview!
There is a simple version of O(n^4).
The idea is to calculate every rectangle [[r1,c1], [r2,c2]], and simply pick the max area <= k.
An improved version takes O(n^3logn). It borrows the idea to find max subarray with sum <= k in 1D array, and apply here: we find all rectangles bounded between r1 & r2, with columns from 0 to end. Pick a pair from tree.
I remember the interviewer said there could be an even better solution, but I haven't figured that out...

Solution I, O(n^4):

``````public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int rows = matrix.length, cols = matrix[0].length;
int[][] areas = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int area = matrix[r][c];
if (r-1 >= 0)
area += areas[r-1][c];
if (c-1 >= 0)
area += areas[r][c-1];
if (r-1 >= 0 && c-1 >= 0)
area -= areas[r-1][c-1];
areas[r][c] = area;
}
}
int max = Integer.MIN_VALUE;
for (int r1 = 0; r1 < rows; r1++) {
for (int c1 = 0; c1 < cols; c1++) {
for (int r2 = r1; r2 < rows; r2++) {
for (int c2 = c1; c2 < cols; c2++) {
int area = areas[r2][c2];
if (r1-1 >= 0)
area -= areas[r1-1][c2];
if (c1-1 >= 0)
area -= areas[r2][c1-1];
if (r1-1 >= 0 && c1 -1 >= 0)
area += areas[r1-1][c1-1];
if (area <= k)
max = Math.max(max, area);
}
}
}
}
return max;
}
``````

Solution II (O(n^3logn)

``````public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int rows = matrix.length, cols = matrix[0].length;
int[][] areas = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int area = matrix[r][c];
if (r-1 >= 0)
area += areas[r-1][c];
if (c-1 >= 0)
area += areas[r][c-1];
if (r-1 >= 0 && c-1 >= 0)
area -= areas[r-1][c-1];
areas[r][c] = area;
}
}
int max = Integer.MIN_VALUE;
for (int r1 = 0; r1 < rows; r1++) {
for (int r2 = r1; r2 < rows; r2++) {
TreeSet<Integer> tree = new TreeSet<>();
for (int c = 0; c < cols; c++) {
int area = areas[r2][c];
if (r1-1 >= 0)
area -= areas[r1-1][c];
Integer ceiling = tree.ceiling(area - k);
if (ceiling != null)
max = Math.max(max, area - ceiling);
}
}
}
return max;
}``````

• Were you asked this question in phone interview or onsite? And may I ask what result you got?

• During on-site. I gave the result as posted :)

• hi, why we need this step " tree.add(0); // padding" ?

• to get area of a rectangle, i use a large area to subtract a smaller area on the left.
we add a padding area of 0 to enable the case where the large area is the rectangle without a smaller area on the left to subtract; that is, the rectangle's left column is column 0.

• I was gave this question in phone interview...........

• you truly interviewed like a boss.

• Nice solution! I think the only improvement is to consider the difference between number of rows and cols.

• The second solution is not getting accepted. I just copy pasted the code, and I am getting "Time Limit Exceeded".

• @mishrasonu1993 : I just tried and it seems to be accepted. Maybe you can try resubmit?

• I converted 2 solutions to C++ and found both of them got TLE. Seems judge has more strict time requirement to C++ implementation.

• @april.rongchen not sure whether someone has replied to you. Anyhow, here is my thought:
with that padding, you will not miss the case when area == k.

• Great idea for transferring this problem to 1D sub array problem! But any idea why the n^3logn solution costs much more time than dp solution? For my submission, dp(n^4) cost 230ms, while n^3logn costs 700+ms

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.