HardArrayBinary SearchMatrixOrdered SetPrefix Sum

Max Sum of Rectangle No Larger Than K

1 approach, code in every language

You are given an m by n integer matrix and an integer k. Consider every axis-aligned rectangle within the matrix and compute the sum of the values it covers.

Return the largest such rectangle sum that does not exceed k. It is guaranteed that at least one rectangle has a sum no larger than k.

A rectangle is defined by choosing a contiguous range of rows and a contiguous range of columns.

Example 1

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

Output: 2

The rectangle formed by columns 1 and 2 across both rows has sum 0 + 1 + (-2) + 3 = 2, which is the largest sum that stays at or below k = 2.

Example 2

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

Output: 3

The two-column rectangle [2, 2] sums to 4, which exceeds k, so it is rejected. The full row [2, 2, -1] sums to 3, which equals k, so 3 is the largest sum not exceeding k.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-10^5 <= k <= 10^5

Fix Column Pair + Ordered Prefix Sums

Collapse the 2D problem into repeated 1D best-subarray-sum-at-most-k queries by fixing each pair of columns.

Loading animation…

Intuition

Any rectangle is bounded by a left and a right column, so we iterate over every pair (left, right). For a fixed pair we compress each row into a single number: the sum of that row's entries between left and right. That turns the task into finding the maximum subarray sum not exceeding k over a 1D array. Using running prefix sums, a subarray sum equals currentPrefix minus some earlier prefix; to keep it at most k we need the smallest earlier prefix that is at least currentPrefix minus k. Storing seen prefixes in an ordered structure lets us binary search for that value quickly, and languages without a built-in ordered set can maintain a sorted list with binary insertion instead.

Algorithm walkthrough

1Loop over every left column; reset a rowSums array of length equal to the number of rows to all zeros.
2For each right column from left onward, add matrix[r][right] into rowSums[r] so rowSums holds the compressed strip between left and right.
3Scan rowSums building a running prefix; start an ordered set of prefixes containing 0.
4At each step, search the ordered set for the smallest prefix that is at least currentPrefix minus k; if found, currentPrefix minus that prefix is a candidate answer, and we keep the best candidate that does not exceed k.
5Insert the current prefix into the ordered set and continue.
6After all column pairs are processed, return the best answer found.

Implementation

import bisect
from typing import List

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        rows, cols = len(matrix), len(matrix[0])
        best = float('-inf')
        for left in range(cols):
            row_sums = [0] * rows
            for right in range(left, cols):
                for r in range(rows):
                    row_sums[r] += matrix[r][right]
                # Best subarray sum <= k via sorted prefixes
                prefixes = [0]
                prefix = 0
                for s in row_sums:
                    prefix += s
                    idx = bisect.bisect_left(prefixes, prefix - k)
                    if idx < len(prefixes):
                        best = max(best, prefix - prefixes[idx])
                    bisect.insort(prefixes, prefix)
        return best

Time

O(rows^2 * cols * log rows) when rows <= cols (transpose otherwise)

Space

O(rows)

There are O(cols^2) column pairs, and each 1D pass runs in O(rows log rows) using ordered prefixes. Iterating over the smaller dimension for the column pairs keeps the bound tight.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free