Max Sum of Rectangle No Larger Than K

Hard
1553.

Max Sum of Rectangle No Larger Than K

Max Sum of Rectangle No Larger Than K is a hard coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.

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?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var maxSumSubmatrix = function(matrix, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Max Sum of Rectangle No Larger Than K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Max Sum of Rectangle No Larger Than K is a hard coding problem on arrays, binary search and matrix, asked in Amazon, Google and Microsoft interviews.

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?

Hints for Max Sum of Rectangle No Larger Than K

  1. Hint 1

    Fix a top row and a bottom row. Squashing the band between them into one array of column sums turns the problem into a 1D one.

  2. Hint 2

    In 1D: the sum of cols[i+1..j] is prefix[j] - prefix[i]. You want the largest such difference that is <= k.

  3. Hint 3

    Scan the prefixes left to right and keep the earlier ones in a sorted structure; for prefix[j], the best partner is the smallest earlier prefix that is >= prefix[j] - k.

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

Java

public static int maxSumSubmatrix(int[][] matrix, int k) {
    int m = matrix.length, n = matrix[0].length;
    int best = Integer.MIN_VALUE;
    for (int top = 0; top < m; top++) {
        int[] cols = new int[n];
        for (int bottom = top; bottom < m; bottom++) {
            for (int c = 0; c < n; c++) cols[c] += matrix[bottom][c];
            TreeSet<Integer> seen = new TreeSet<>();
            seen.add(0);
            int prefix = 0;
            for (int c = 0; c < n; c++) {
                prefix += cols[c];
                Integer q = seen.ceiling(prefix - k);
                if (q != null) best = Math.max(best, prefix - q);
                seen.add(prefix);
            }
            if (best == k) return k;
        }
    }
    return best;
}

C++

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
    int m = matrix.size(), n = matrix[0].size();
    int best = INT_MIN;
    for (int top = 0; top < m; top++) {
        vector<int> cols(n, 0);
        for (int bottom = top; bottom < m; bottom++) {
            for (int c = 0; c < n; c++) cols[c] += matrix[bottom][c];
            set<int> seen;
            seen.insert(0);
            int prefix = 0;
            for (int c = 0; c < n; c++) {
                prefix += cols[c];
                auto it = seen.lower_bound(prefix - k);
                if (it != seen.end()) best = max(best, prefix - *it);
                seen.insert(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search