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.lengthn == matrix[i].length1 <= 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?
Problem Overview: You are given a 2D matrix and an integer k. The task is to find the maximum possible sum of any rectangular submatrix such that the sum does not exceed k. The challenge comes from efficiently exploring all rectangle combinations without exceeding time limits.
Approach 1: Prefix Sum with Iteration (Brute Force Optimization) (O(m^2 * n^2) time, O(1) extra space)
Compute a prefix sum matrix so you can calculate any rectangle sum in constant time. Iterate over every possible pair of top-left and bottom-right coordinates. For each pair, compute the rectangle sum using the prefix matrix and track the largest value that does not exceed k. This removes repeated summations but still checks all rectangles, leading to quadratic choices for rows and columns.
Approach 2: Prefix Sum + Ordered Set with Binary Search (Optimal) (O(cols^2 * rows log rows) time, O(rows) space)
Fix two column boundaries and compress the rows between them into a 1D array of cumulative sums. The problem then becomes: find the maximum subarray sum no larger than k. Maintain prefix sums and store them in an ordered structure (like a balanced BST or TreeSet). For each running prefix sum s, search for the smallest prefix ≥ s - k using binary search. This guarantees the largest valid subarray sum ending at the current row. Repeat for every column pair. The ordered structure is the key insight that avoids checking every subarray.
Approach 3: Recursive Approach with Memoization (O(m * n * states) time, O(m * n) space)
A recursive formulation explores rectangle boundaries while caching intermediate sums using memoization. Each recursive call expands a rectangle by adjusting row or column limits and stores previously computed sums to avoid recomputation. While memoization reduces duplicate work, the state space still grows quickly for large matrices. This approach is mainly useful for conceptual understanding or smaller constraints rather than optimal performance.
Recommended for interviews: The prefix-sum + ordered set solution is the expected answer. Interviewers want to see how you reduce the 2D rectangle problem into a 1D subarray constraint and then solve it using prefix sums and an ordered set. Explaining the brute force prefix-sum approach first shows problem decomposition, while the ordered-set optimization demonstrates strong algorithmic thinking.
This approach involves calculating the prefix sum for every column and iterating over pairs of row indices to form vertical strips. The idea is derived from simplifying the multidimensional problem to a manageable form by transforming it into a 1D problem with the help of prefix sums and leveraging subarray sum computation techniques.
The Python implementation uses a 2D prefix sum to convert the problem into finding a subarray sum no larger than k. We iterate over left and right column boundaries and compute row-wise sums in between. Then maxSumNoLargerThanK finds the maximum subarray sum no larger than k in these running row sums using a binary search approach (with the help of Python's bisect library) to maintain the cumulative sum.
Time Complexity: O(n^2 * m log m), where m = num of rows and n = num of columns. Space Complexity: O(m) for storing row sums.
This approach uses recursion to solve the problem by breaking it down into smaller subproblems and storing the results of these subproblems to avoid redundant calculations. Hence, it combines recursion with memoization.
The C solution initializes a memo array to store intermediate results. The solve function checks if the value is already computed to avoid recalculating it, and recursively calculates values as needed.
Time Complexity: O(n)
Space Complexity: O(n) due to the memoization array
This approach solves the problem iteratively, preventing the overhead of recursive function calls. It constructs a solution bottom-up and is generally more space-efficient.
The C solution iteratively calculates Fibonacci numbers using constant space, which makes it efficient for larger values of n.
Time Complexity: O(n)
Space Complexity: O(1)
We can enumerate the upper and lower boundaries i and j of the rectangle, then calculate the sum of the elements in each column within this boundary, and record it in the array nums. The problem is transformed into how to find the maximum subarray sum not exceeding k in the array nums.
We can use an ordered set to quickly find the maximum value less than or equal to x, thereby obtaining a subarray with the maximum subarray sum not exceeding k.
The time complexity is O(m^2 times n times log n), and the space complexity is O(n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix Sum with Iteration | Time Complexity: O(n^2 * m log m), where m = num of rows and n = num of columns. Space Complexity: O(m) for storing row sums. |
| Recursive Approach with Memoization | Time Complexity: O(n) |
| Iterative Approach | Time Complexity: O(n) |
| Enumerate Boundaries + Ordered Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum with Iteration | O(m^2 * n^2) | O(1) | Simple implementation and good for understanding rectangle prefix sums |
| Prefix Sum + Ordered Set (Binary Search) | O(cols^2 * rows log rows) | O(rows) | Best general solution for large matrices and typical interview expectations |
| Recursive with Memoization | O(m * n * states) | O(m * n) | Useful for conceptual exploration or smaller input sizes |
Max Sum of Rectangle No Larger Than K | Leetcode 363 | Live coding session • Coding Decoded • 13,072 views views
Watch 9 more video solutions →Practice Max Sum of Rectangle No Larger Than K with our built-in code editor and test cases.
Practice on FleetCode