Get started

Max Sum of Rectangle No Larger Than K — Hard Problem & Solution

Given an m x n integer matrix matrix and an integer k, consider every non-empty axis-aligned rectangle of cells inside the matrix.

Problem statement

Given an m x n integer matrix matrix and an integer k, consider every non-empty axis-aligned rectangle of cells inside the matrix. Return the largest rectangle sum that is no larger than k.

The input guarantees that at least one rectangle has a sum <= k.

Example 1

Input: matrix = [[2,-1,3],[-4,5,1]], k = 4
Output: 4
Explanation: The whole first row sums to 2 - 1 + 3 = 4, the largest value allowed. The column `[3,1]` sums to 4 as well.

Example 2

Input: matrix = [[3,3,-1]], k = 5
Output: 5
Explanation: `[3,3,-1]` sums to 5; `[3,3]` sums to 6, which is too large.

Example 3

Input: matrix = [[5,-2],[-1,4]], k = 0
Output: -1

Constraints

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

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

How to solve Max Sum of Rectangle No Larger Than K

Reduce to 1D by fixing the row band, then answer "max subarray sum <= k" with prefix sums and an ordered set — the smallest earlier prefix that is at least prefix - k gives the best subarray ending here.

Approach

  1. For every pair of rows top <= bottom, maintain cols[c] = the sum of column c between them (add row bottom as it grows).
  2. Start a sorted set holding the empty prefix 0 and a running prefix p = 0.
  3. For each column, add cols[c] to p; find the smallest q in the set with q >= p - k. If it exists, p - q is a candidate — keep the maximum.
  4. Insert p into the set and continue. Stop early if the answer ever equals k.

Why it works

Every rectangle is a row band plus a column range, and every column range's sum is a difference of two prefixes of the band's column sums. For a fixed right end the difference p - q is largest when q is smallest, subject to p - q <= k, i.e. q >= p - k — exactly the ceiling query. So every rectangle is considered implicitly and the best valid one is found.

Complexity

  • Time — O(m² · n log n)
  • Space — O(n)

Pitfalls

  • Kadane's algorithm finds the maximum subarray but cannot respect the <= k cap — the ordered-set search is what handles it.
  • Seed the set with 0, or subarrays that start at the first column are missed.
  • The answer can be negative; do not initialise the best value with 0.

Reference solution

Python

from typing import List
import bisect

def maxSumSubmatrix(matrix: List[List[int]], k: int) -> int:
    m, n = len(matrix), len(matrix[0])
    best = None
    for top in range(m):
        cols = [0] * n
        for bottom in range(top, m):
            row = matrix[bottom]
            for c in range(n):
                cols[c] += row[c]
            seen = [0]
            prefix = 0
            for v in cols:
                prefix += v
                i = bisect.bisect_left(seen, prefix - k)
                if i < len(seen):
                    cand = prefix - seen[i]
                    if best is None or cand > best:
                        best = cand
                bisect.insort(seen, prefix)
            if best == k:
                return k
    return best

JavaScript

var maxSumSubmatrix = function(matrix, k) {
    var m = matrix.length, n = matrix[0].length, best = -Infinity;
    var lowerBound = function(a, x) {
        var lo = 0, hi = a.length;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (a[mid] < x) lo = mid + 1; else hi = mid;
        }
        return lo;
    };
    for (var top = 0; top < m; top++) {
        var cols = new Array(n).fill(0);
        for (var bottom = top; bottom < m; bottom++) {
            for (var c = 0; c < n; c++) cols[c] += matrix[bottom][c];
            var seen = [0], prefix = 0;
            for (var j = 0; j < n; j++) {
                prefix += cols[j];
                var i = lowerBound(seen, prefix - k);
                if (i < seen.length && prefix - seen[i] > best) best = prefix - seen[i];
                seen.splice(lowerBound(seen, prefix), 0, prefix);
            }
            if (best === k) return k;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search