Problem Description

Given a 2D matrix of integers matrix and an integer k, find the maximum sum of a rectangle (submatrix) within the matrix such that its sum is no larger than k. The rectangle must be made up of contiguous rows and columns. You may assume that at least one rectangle exists with sum no larger than k.

• The rectangle can be as small as a single element or as large as the entire matrix.
• The sum must not exceed k.
• All elements must be used at most once per rectangle (no reuse).
• Return the maximum such sum possible.

Example:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: The rectangle [[0, 1], [-2, 3]] has sum 2 and is the max no larger than k.

Thought Process

At first glance, one might consider checking every possible rectangle in the matrix, calculating its sum, and comparing it with k. However, this brute-force approach would be extremely slow for larger matrices because the number of rectangles grows rapidly with matrix size.

To optimize, we can draw inspiration from 1D subarray sum problems, particularly the "Maximum Subarray Sum No Larger Than K" problem. By reducing the 2D problem to a series of 1D problems (using row or column boundaries), we can leverage efficient algorithms for the 1D case. The key insight is to fix two boundaries (rows or columns), collapse the matrix between them into a 1D array of sums, and then solve the 1D version for that array.

For the 1D case, finding the max subarray sum no larger than k can be efficiently solved using prefix sums and a sorted data structure (like a TreeSet in Java, or bisect in Python).

Solution Approach

We solve the problem in two main steps:

1. Reduce the 2D problem to 1D: For every pair of left and right column boundaries, collapse the matrix into a 1D array where each element is the sum between those columns for each row.
2. Solve the 1D max subarray sum ≤ k problem: For the collapsed array, use prefix sums and a sorted container to efficiently find the maximum subarray sum no larger than k.

Step-by-step:

• Iterate over all pairs of columns (left and right).
• For each pair, create an array rowSums of size equal to the number of rows, initialized to 0.
• For each column between left and right (inclusive), add the column's values to rowSums.
• Now, the problem reduces to finding the max sum of a subarray in rowSums that is ≤ k.
• To solve this, use prefix sums and insert them in sorted order. For each new prefix sum, look for the smallest prefix sum in the set such that the difference is ≤ k. This can be done efficiently using binary search.
• Keep track of the maximum sum found so far.

Why this works: By fixing columns and collapsing rows, we transform the problem into a more manageable form. The prefix sum and binary search trick ensures we efficiently find the best subarray sum for each configuration.

Example Walkthrough

Let's use the sample input: matrix = [[1,0,1],[0,-2,3]], k = 2.

1. First, fix left = 0. For right = 0:
   • rowSums = [1, 0]
   • Find max subarray sum ≤ 2: possible sums are 1 (row 0), 0 (row 1), 1 (rows 0-1). Max is 1.
2. Next, right = 1:
   • rowSums = [1+0, 0+(-2)] = [1, -2]
   • Possible subarrays: 1, -2, -1 (rows 0-1). Max is 1.
3. Next, right = 2:
   • rowSums = [1+0+1, 0+(-2)+3] = [2, 1]
   • Possible subarrays: 2, 1, 3 (rows 0-1). 3 is too large, so max is 2.
4. Repeat for left = 1 and left = 2. The maximum found remains 2.

Thus, the answer is 2.

Time and Space Complexity

Brute-force approach:
- Enumerate all possible rectangles: O(m² n²) (for m rows, n columns).
- For each rectangle, sum all elements: up to O(mn) per rectangle.
- Total: O(m³ n³), which is impractical for large matrices.

Optimized approach:
- We fix two columns: O(n²) pairs.
- For each pair, we process a 1D array of size m.
- For each, we use prefix sums and maintain a sorted list/set (insertion/search O(log m)).
- So per column pair, it's O(m log m).
- Total: O(n² m log m).

Space Complexity:
- O(m) for the row sums and prefix set.

Summary

By reducing the problem from 2D to 1D and leveraging efficient prefix sum and binary search techniques, we transform a potentially infeasible brute-force approach into an elegant and efficient solution. The key is recognizing that, for each pair of columns, the problem becomes a classic subarray sum problem, which we can solve optimally with the right data structures.

Code Implementation

import bisect

class Solution:
    def maxSumSubmatrix(self, matrix, k):
        if not matrix or not matrix[0]:
            return 0
        maxSum = float('-inf')
        rows, cols = len(matrix), len(matrix[0])
        for left in range(cols):
            rowSums = [0] * rows
            for right in range(left, cols):
                for i in range(rows):
                    rowSums[i] += matrix[i][right]
                # Find the max subarray no larger than k
                prefixSums = [0]
                currSum = 0
                currMax = float('-inf')
                for sum_ in rowSums:
                    currSum += sum_
                    # We want smallest prefix >= currSum - k
                    idx = bisect.bisect_left(prefixSums, currSum - k)
                    if idx < len(prefixSums):
                        currMax = max(currMax, currSum - prefixSums[idx])
                    bisect.insort(prefixSums, currSum)
                maxSum = max(maxSum, currMax)
        return maxSum
      

#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int maxSum = INT_MIN;
        int rows = matrix.size(), cols = matrix[0].size();
        for (int left = 0; left < cols; ++left) {
            vector<int> rowSums(rows, 0);
            for (int right = left; right < cols; ++right) {
                for (int i = 0; i < rows; ++i) {
                    rowSums[i] += matrix[i][right];
                }
                set<int> prefixSums;
                prefixSums.insert(0);
                int currSum = 0, currMax = INT_MIN;
                for (int sum : rowSums) {
                    currSum += sum;
                    auto it = prefixSums.lower_bound(currSum - k);
                    if (it != prefixSums.end()) {
                        currMax = max(currMax, currSum - *it);
                    }
                    prefixSums.insert(currSum);
                }
                maxSum = max(maxSum, currMax);
            }
        }
        return maxSum;
    }
};
      

import java.util.TreeSet;

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int maxSum = Integer.MIN_VALUE;
        int rows = matrix.length, cols = matrix[0].length;
        for (int left = 0; left < cols; left++) {
            int[] rowSums = new int[rows];
            for (int right = left; right < cols; right++) {
                for (int i = 0; i < rows; i++) {
                    rowSums[i] += matrix[i][right];
                }
                TreeSet<Integer> prefixSums = new TreeSet<>();
                prefixSums.add(0);
                int currSum = 0, currMax = Integer.MIN_VALUE;
                for (int sum : rowSums) {
                    currSum += sum;
                    Integer num = prefixSums.ceiling(currSum - k);
                    if (num != null) {
                        currMax = Math.max(currMax, currSum - num);
                    }
                    prefixSums.add(currSum);
                }
                maxSum = Math.max(maxSum, currMax);
            }
        }
        return maxSum;
    }
}
      

function maxSumSubmatrix(matrix, k) {
    if (!matrix.length || !matrix[0].length) return 0;
    let maxSum = -Infinity;
    let rows = matrix.length, cols = matrix[0].length;
    for (let left = 0; left < cols; left++) {
        let rowSums = new Array(rows).fill(0);
        for (let right = left; right < cols; right++) {
            for (let i = 0; i < rows; i++) {
                rowSums[i] += matrix[i][right];
            }
            // Find the max subarray no larger than k
            let prefixSums = [0];
            let currSum = 0, currMax = -Infinity;
            for (let sum of rowSums) {
                currSum += sum;
                let idx = lowerBound(prefixSums, currSum - k);
                if (idx < prefixSums.length) {
                    currMax = Math.max(currMax, currSum - prefixSums[idx]);
                }
                insert(prefixSums, currSum);
            }
            maxSum = Math.max(maxSum, currMax);
        }
    }
    return maxSum;
}

// Helper: binary search for lower bound
function lowerBound(arr, target) {
    let l = 0, r = arr.length;
    while (l < r) {
        let m = l + ((r - l) >> 1);
        if (arr[m] < target) l = m + 1;
        else r = m;
    }
    return l;
}

// Helper: insert in sorted order
function insert(arr, val) {
    let idx = lowerBound(arr, val);
    arr.splice(idx, 0, val);
}