# Max Sum of Rectangle No Larger Than K
**Difficulty:** HARD
[External](https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k)
Canonical: https://scaleengineer.com/dsa/problems/max-sum-of-rectangle-no-larger-than-k
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Matrix, Ordered Set
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Given an `m x n` matrix `matrix` and an integer `k`, return _the max sum of a rectangle in the matrix such that its sum is no larger than_ `k`.

It is **guaranteed** that there will be a rectangle with a sum no larger than `k`.

**Example 1:**

![](https://assets.glich.co/dsa/max-sum-of-rectangle-no-larger-than-k/image0.jpg) 

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

**Example 2:**

**Input:** matrix = [[2,2,-1]], k = 3
**Output:** 3

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 100`
* `-100 <= matrix[i][j] <= 100`
* `-105 <= k <= 105`

**Follow up:** What if the number of rows is much larger than the number of columns?

# Approaches
## Brute Force with 2D Prefix Sums
This approach involves checking every possible rectangle within the matrix. To avoid re-calculating the sum of each rectangle from scratch, which would be very inefficient, we can pre-compute a 2D prefix sum array (also known as a summed-area table). This table allows us to find the sum of any rectangle in constant `O(1)` time.
**Time:** O(m^2 * n^2). The pre-computation of the sum matrix is `O(m*n)`, but this is dominated by the four nested loops required to define and check every possible rectangle. · **Space:** O(m * n) to store the 2D prefix sum matrix.
**Pros:** Conceptually simpler to understand and implement than more optimal solutions.; Improves upon a naive `O(m^3 * n^3)` brute-force approach by using prefix sums.
**Cons:** The time complexity is too high for the given constraints (`m, n <= 100`), and this solution will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
First, we create a `(m+1) x (n+1)` prefix sum matrix, let's call it `sums`. `sums[i][j]` will store the sum of all elements in the rectangle from the top-left corner `(0, 0)` to `(i-1, j-1)`. This `sums` matrix can be populated in `O(m*n)` time using a dynamic programming recurrence relation. After the `sums` matrix is built, we iterate through all possible rectangles. A rectangle is defined by its top-left corner `(r1, c1)` and its bottom-right corner `(r2, c2)`. This requires four nested loops. For each rectangle, we calculate its sum in `O(1)` using the pre-computed `sums` matrix. If this sum is less than or equal to `k`, we compare it with our current maximum sum found so far and update it if the current sum is larger. We initialize the maximum sum to a very small number to handle negative matrix elements correctly. Since the problem guarantees a solution exists, we will always find a valid sum.

```java
class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] sums = new int[rows + 1][cols + 1];

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                sums[i][j] = matrix[i - 1][j - 1] +
                             sums[i - 1][j] +
                             sums[i][j - 1] -
                             sums[i - 1][j - 1];
            }
        }

        int maxSum = Integer.MIN_VALUE;
        for (int r1 = 1; r1 <= rows; r1++) {
            for (int c1 = 1; c1 <= cols; c1++) {
                for (int r2 = r1; r2 <= rows; r2++) {
                    for (int c2 = c1; c2 <= cols; c2++) {
                        int currentSum = sums[r2][c2] -
                                         sums[r1 - 1][c2] -
                                         sums[r2][c1 - 1] +
                                         sums[r1 - 1][c1 - 1];
                        if (currentSum <= k) {
                            maxSum = Math.max(maxSum, currentSum);
                        }
                    }
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- 1. Create a `(m+1) x (n+1)` prefix sum matrix `sums`.
- 2. Populate `sums` in `O(m*n)` time using the formula: `sums[i][j] = matrix[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]`.
- 3. Initialize `max_sum = Integer.MIN_VALUE`.
- 4. Use four nested loops to iterate through all possible top-left `(r1, c1)` and bottom-right `(r2, c2)` corners of a rectangle.
- 5. For each rectangle, calculate its sum in `O(1)` using the `sums` matrix: `current_sum = sums[r2+1][c2+1] - sums[r1][c2+1] - sums[r2+1][c1] + sums[r1][c1]`.
- 6. If `current_sum <= k`, update `max_sum = Math.max(max_sum, current_sum)`.
- 7. Return `max_sum`.

## Optimized Approach using 1D Reduction and Binary Search
A more efficient approach reduces the 2D problem into a 1D problem. We can fix the left and right boundaries of our rectangle and then treat the problem as finding the maximum sum subarray within the 1D array formed by summing up the rows between these boundaries. This 1D subproblem, "find maximum subarray sum no larger than k", can be solved efficiently using prefix sums and a balanced binary search tree (like Java's `TreeSet`).
**Time:** O(min(m,n)^2 * max(m,n) * log(max(m,n))). The two outer loops iterate `O(min(m,n)^2)` times. Inside, we update a 1D array of size `max(m,n)` (which takes `O(max(m,n))`) and then process it with the helper function, which takes `O(max(m,n) * log(max(m,n)))`. · **Space:** O(max(m, n)). This space is used for the temporary 1D array (`rowSums` or `colSums`) and the `TreeSet` which stores at most `max(m, n) + 1` prefix sums.
**Pros:** Much more efficient and passes the time limits for the given constraints.; Effectively addresses the follow-up question by choosing the optimal iteration strategy based on matrix dimensions.
**Cons:** The algorithm is significantly more complex to conceptualize and implement correctly compared to the brute-force method.
### Explanation
The core idea is to iterate through all possible column pairs `(left, right)` that define the horizontal boundaries of our rectangles. For each pair, we compute a 1D array, let's call it `rowSums`, where `rowSums[i]` is the sum of elements in `matrix[i]` from column `left` to `right`. As we iterate the `right` column from `left` to `n-1`, we can update `rowSums` in `O(m)` time by adding the values from the new `right` column. For each updated `rowSums` array, we solve the 1D subproblem: find the maximum subarray sum that is no larger than `k`.

**Solving the 1D Subproblem:** We can solve this in `O(m log m)` time. We iterate through `rowSums`, maintaining a `currentSum` (the prefix sum). For each `currentSum`, we need to find a `prevSum` from the set of previously encountered prefix sums such that `currentSum - prevSum <= k`. To maximize this difference, we need the smallest `prevSum` that satisfies `prevSum >= currentSum - k`. A `TreeSet` is ideal for this, as its `ceiling()` method can find this value in `O(log m)` time.

**Follow-up Optimization:** The overall time complexity would be `O(n^2 * m log m)`. If the number of rows `m` is much larger than the number of columns `n`, this is inefficient. We can optimize by always choosing the smaller dimension for the outer loops. If `m > n`, we iterate through row pairs `(top, bottom)` and create 1D arrays of column sums. This ensures the complexity is always `O(min(m,n)^2 * max(m,n) * log(max(m,n)))`.

```java
import java.util.TreeSet;

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSum = Integer.MIN_VALUE;

        // Iterate over the smaller dimension for the outer loops to optimize
        boolean iterateByCols = cols >= rows;

        if (iterateByCols) {
            // Iterate through all possible pairs of columns (left, right)
            for (int left = 0; left < cols; left++) {
                int[] rowSums = new int[rows];
                for (int right = left; right < cols; right++) {
                    // Update rowSums to include the 'right' column
                    for (int i = 0; i < rows; i++) {
                        rowSums[i] += matrix[i][right];
                    }
                    // Find the max subarray sum in rowSums no larger than k
                    maxSum = Math.max(maxSum, findMaxSubarraySumNoLargerThanK(rowSums, k));
                    if (maxSum == k) return k; // Early exit optimization
                }
            }
        } else { // iterate by rows
            // Iterate through all possible pairs of rows (top, bottom)
            for (int top = 0; top < rows; top++) {
                int[] colSums = new int[cols];
                for (int bottom = top; bottom < rows; bottom++) {
                    // Update colSums to include the 'bottom' row
                    for (int j = 0; j < cols; j++) {
                        colSums[j] += matrix[bottom][j];
                    }
                    // Find the max subarray sum in colSums no larger than k
                    maxSum = Math.max(maxSum, findMaxSubarraySumNoLargerThanK(colSums, k));
                    if (maxSum == k) return k; // Early exit optimization
                }
            }
        }
        return maxSum;
    }

    // Helper function to solve the 1D version of the problem in O(N log N)
    private int findMaxSubarraySumNoLargerThanK(int[] arr, int k) {
        int maxSum = Integer.MIN_VALUE;
        TreeSet<Integer> prefixSums = new TreeSet<>();
        prefixSums.add(0); // To handle subarrays that start from index 0
        int currentSum = 0;

        for (int val : arr) {
            currentSum += val;
            // We seek a prevSum such that: currentSum - prevSum <= k
            // This is equivalent to: prevSum >= currentSum - k
            // We need the smallest such prevSum to maximize (currentSum - prevSum).
            Integer prevSum = prefixSums.ceiling(currentSum - k);

            if (prevSum != null) {
                maxSum = Math.max(maxSum, currentSum - prevSum);
            }
            
            prefixSums.add(currentSum);
        }
        return maxSum;
    }
}
```
### Algorithm
- 1. To handle the follow-up, determine if `rows` or `cols` is smaller. The outer loops will iterate over the smaller dimension. Let's assume `cols >= rows`.
- 2. Initialize `max_sum = Integer.MIN_VALUE`.
- 3. Iterate `left` from `0` to `cols-1`.
- 4. Inside, initialize a 1D array `rowSums` of size `rows` to all zeros.
- 5. Iterate `right` from `left` to `cols-1`.
- 6. For the current `(left, right)` pair, update `rowSums` by adding the elements of the `right`-th column.
- 7. Call a helper function `findMaxSubarraySumNoLargerThanK` on the `rowSums` array and `k`.
    - a. In the helper, initialize a `TreeSet` `prefixSums` and add `0`.
    - b. Initialize `currentSum = 0` and `maxSubarraySum = Integer.MIN_VALUE`.
    - c. Iterate through the `rowSums` array. For each element, update `currentSum`.
    - d. Find `target = prefixSums.ceiling(currentSum - k)`.
    - e. If `target` exists, update `maxSubarraySum = max(maxSubarraySum, currentSum - target)`.
    - f. Add `currentSum` to `prefixSums`.
    - g. Return `maxSubarraySum`.
- 8. Update the overall `max_sum` with the result from the helper function.
- 9. Return `max_sum`.

# Solutions
### Java

```java
class Solution {
public
  int maxSumSubmatrix(int[][] matrix, int k) {
    int m = matrix.length;
    int n = matrix[0].length;
    final int inf = 1 << 30;
    int ans = -inf;
    for (int i = 0; i < m; ++i) {
      int[] nums = new int[n];
      for (int j = i; j < m; ++j) {
        for (int h = 0; h < n; ++h) {
          nums[h] += matrix[j][h];
        }
        int s = 0;
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(0);
        for (int x : nums) {
          s += x;
          Integer y = ts.ceiling(s - k);
          if (y != null) {
            ans = Math.max(ans, s - y);
          }
          ts.add(s);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
    int m = matrix.size(), n = matrix[0].size();
    const int inf = 1 << 30;
    int ans = -inf;
    for (int i = 0; i < m; ++i) {
      vector<int> nums(n);
      for (int j = i; j < m; ++j) {
        for (int h = 0; h < n; ++h) {
          nums[h] += matrix[j][h];
        }
        set<int> ts;
        int s = 0;
        ts.insert(0);
        for (int x : nums) {
          s += x;
          auto it = ts.lower_bound(s - k);
          if (it != ts.end()) {
            ans = max(ans, s - *it);
          }
          ts.insert(s);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
from sortedcontainers import SortedSet class Solution : def maxSumSubmatrix ( self , matrix : List [ List [ int ]], k : int ) -> int : m , n = len ( matrix ), len ( matrix [ 0 ]) ans = - inf for i in range ( m ): nums = [ 0 ] * n for j in range ( i , m ): for h in range ( n ): nums [ h ] += matrix [ j ][ h ] s = 0 ts = SortedSet ([ 0 ]) for x in nums : s += x p = ts . bisect_left ( s - k ) if p != len ( ts ): ans = max ( ans , s - ts [ p ]) ts . add ( s ) return ans
```