Max Sum of Rectangle No Larger Than K

Hard

#0350Time: 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.1 company

Patterns

Prefix Sum

Algorithms

Binary Search

Data structures

Array Matrix Ordered Set

Companies

DE Shaw

Prompt

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:

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
-10⁵ <= k <= 10⁵

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Create a (m+1) x (n+1) prefix sum matrix sums.
1. 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].
1. Initialize max_sum = Integer.MIN_VALUE.
1. Use four nested loops to iterate through all possible top-left (r1, c1) and bottom-right (r2, c2) corners of a rectangle.
1. 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].
1. If current_sum <= k, update max_sum = Math.max(max_sum, current_sum).
1. Return max_sum.

Walkthrough

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.

1class Solution {2    public int maxSumSubmatrix(int[][] matrix, int k) {3        int rows = matrix.length;4        int cols = matrix[0].length;5        int[][] sums = new int[rows + 1][cols + 1];6 7        for (int i = 1; i <= rows; i++) {8            for (int j = 1; j <= cols; j++) {9                sums[i][j] = matrix[i - 1][j - 1] +10                             sums[i - 1][j] +11                             sums[i][j - 1] -12                             sums[i - 1][j - 1];13            }14        }15 16        int maxSum = Integer.MIN_VALUE;17        for (int r1 = 1; r1 <= rows; r1++) {18            for (int c1 = 1; c1 <= cols; c1++) {19                for (int r2 = r1; r2 <= rows; r2++) {20                    for (int c2 = c1; c2 <= cols; c2++) {21                        int currentSum = sums[r2][c2] -22                                         sums[r1 - 1][c2] -23                                         sums[r2][c1 - 1] +24                                         sums[r1 - 1][c1 - 1];25                        if (currentSum <= k) {26                            maxSum = Math.max(maxSum, currentSum);27                        }28                    }29                }30            }31        }32        return maxSum;33    }34}

Complexity

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.

Trade-offs

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.

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).

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.
1. Initialize max_sum = Integer.MIN_VALUE.
1. Iterate left from 0 to cols-1.
1. Inside, initialize a 1D array rowSums of size rows to all zeros.
1. Iterate right from left to cols-1.
1. For the current (left, right) pair, update rowSums by adding the elements of the right-th column.
1. 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.
1. Update the overall max_sum with the result from the helper function.
1. Return max_sum.

Walkthrough

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))).

1import java.util.TreeSet;2 3class Solution {4    public int maxSumSubmatrix(int[][] matrix, int k) {5        int rows = matrix.length;6        int cols = matrix[0].length;7        int maxSum = Integer.MIN_VALUE;8 9        // Iterate over the smaller dimension for the outer loops to optimize10        boolean iterateByCols = cols >= rows;11 12        if (iterateByCols) {13            // Iterate through all possible pairs of columns (left, right)14            for (int left = 0; left < cols; left++) {15                int[] rowSums = new int[rows];16                for (int right = left; right < cols; right++) {17                    // Update rowSums to include the 'right' column18                    for (int i = 0; i < rows; i++) {19                        rowSums[i] += matrix[i][right];20                    }21                    // Find the max subarray sum in rowSums no larger than k22                    maxSum = Math.max(maxSum, findMaxSubarraySumNoLargerThanK(rowSums, k));23                    if (maxSum == k) return k; // Early exit optimization24                }25            }26        } else { // iterate by rows27            // Iterate through all possible pairs of rows (top, bottom)28            for (int top = 0; top < rows; top++) {29                int[] colSums = new int[cols];30                for (int bottom = top; bottom < rows; bottom++) {31                    // Update colSums to include the 'bottom' row32                    for (int j = 0; j < cols; j++) {33                        colSums[j] += matrix[bottom][j];34                    }35                    // Find the max subarray sum in colSums no larger than k36                    maxSum = Math.max(maxSum, findMaxSubarraySumNoLargerThanK(colSums, k));37                    if (maxSum == k) return k; // Early exit optimization38                }39            }40        }41        return maxSum;42    }43 44    // Helper function to solve the 1D version of the problem in O(N log N)45    private int findMaxSubarraySumNoLargerThanK(int[] arr, int k) {46        int maxSum = Integer.MIN_VALUE;47        TreeSet<Integer> prefixSums = new TreeSet<>();48        prefixSums.add(0); // To handle subarrays that start from index 049        int currentSum = 0;50 51        for (int val : arr) {52            currentSum += val;53            // We seek a prevSum such that: currentSum - prevSum <= k54            // This is equivalent to: prevSum >= currentSum - k55            // We need the smallest such prevSum to maximize (currentSum - prevSum).56            Integer prevSum = prefixSums.ceiling(currentSum - k);57 58            if (prevSum != null) {59                maxSum = Math.max(maxSum, currentSum - prevSum);60            }61            62            prefixSums.add(currentSum);63        }64        return maxSum;65    }66}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int maxSumSubmatrix(int[][] matrix, int k) {4    int m = matrix.length;5    int n = matrix[0].length;6    final int inf = 1 << 30;7    int ans = -inf;8    for (int i = 0; i < m; ++i) {9      int[] nums = new int[n];10      for (int j = i; j < m; ++j) {11        for (int h = 0; h < n; ++h) {12          nums[h] += matrix[j][h];13        }14        int s = 0;15        TreeSet<Integer> ts = new TreeSet<>();16        ts.add(0);17        for (int x : nums) {18          s += x;19          Integer y = ts.ceiling(s - k);20          if (y != null) {21            ans = Math.max(ans, s - y);22          }23          ts.add(s);24        }25      }26    }27    return ans;28  }29}

1class Solution {2public:3  int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {4    int m = matrix.size(), n = matrix[0].size();5    const int inf = 1 << 30;6    int ans = -inf;7    for (int i = 0; i < m; ++i) {8      vector<int> nums(n);9      for (int j = i; j < m; ++j) {10        for (int h = 0; h < n; ++h) {11          nums[h] += matrix[j][h];12        }13        set<int> ts;14        int s = 0;15        ts.insert(0);16        for (int x : nums) {17          s += x;18          auto it = ts.lower_bound(s - k);19          if (it != ts.end()) {20            ans = max(ans, s - *it);21          }22          ts.insert(s);23        }24      }25    }26    return ans;27  }28};

1from 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem