Skip to main content

363 - Max Sum of Rectangle No Larger Than K

Difficulty: Hard | Pattern: Prefix Sum + Sorted Set | Company tags: Google, Pocket Gems

Problem Statement​

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  (rectangle [[0,1],[-2,3]] has sum 2)

Example 2:

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

Approach: Column Compression + Sorted Set — O(m² n log n)​

Key insight:

  1. Fix left and right column bounds.
  2. Compute row sums between those columns (compress to 1D).
  3. Find subarray sum no larger than k using prefix sums + sorted set (binary search for prefix - k).

Algorithm Flow​

from sortedcontainers import SortedList

def maxSumSubmatrix(matrix: list[list[int]], k: int) -> int:
    m, n = len(matrix), len(matrix[0])
    result = float('-inf')
    
    for left in range(n):
        row_sum = [0] * m
        for right in range(left, n):
            for r in range(m):
                row_sum[r] += matrix[r][right]
            
            # Find max subarray sum no larger than k
            sorted_prefix = SortedList([0])
            prefix = 0
            for s in row_sum:
                prefix += s
                # Find smallest prefix sum such that prefix - prev_prefix <= k
                # i.e., prev_prefix >= prefix - k
                idx = sorted_prefix.bisect_left(prefix - k)
                if idx < len(sorted_prefix):
                    result = max(result, prefix - sorted_prefix[idx])
                sorted_prefix.add(prefix)
    
    return result

Dry Run​

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

Fix left=0, right=1: row_sum = [1+0, 0+(-2)] = [1, -2] Prefix sums: [0, 1, -1]

  • prefix=1: bisect_left([0], 1-2=-1) → idx=0, result=max(-inf, 1-0)=1
  • prefix=-1: bisect_left([0,1], -1-2=-3) → idx=0, result=max(1,-1-0)=1

Fix left=1, right=2: row_sum=[0+1,-2+3]=[1,1]

  • prefix=1: result=max(1,1)=1
  • prefix=2: bisect_left([0,1], 0) → idx=0, result=max(1,2-0)=2 ✓

Result: 2 ✓

Complexity​

  • Time: O(m² n log n) — O(n²) column pairs, O(m log m) per pair
  • Space: O(m)

Key Terms​

TermDefinition
Prefix sumRunning total of elements up to an index, used to compute range sums in O(1).
Column compressionCollapsing a 2D matrix slice between two column bounds into a 1D row-sum array.
Sorted set / bisectOrdered container supporting binary search, used here to find the smallest prefix ≥ prefix - k.
Subarray sum ≤ kClassic 1D subproblem: find the max sum subarray whose sum does not exceed a bound.

FAQ​

Q: Why compress columns instead of brute-forcing all O(n²) rectangles directly? A: Fixing left/right reduces the 2D problem to a 1D "max subarray sum ≤ k" problem, which is solvable in O(m log m) using prefix sums and a sorted set instead of O(m²) brute force per pair.

Q: Why iterate the smaller dimension in the outer O(n²) loop? A: If m < n, fix row bounds instead of column bounds to make the O(dim²) factor apply to the smaller dimension, improving overall runtime.

Q: What does bisect_left(prefix - k) actually find? A: The smallest previously-seen prefix sum p such that prefix - p <= k, which maximizes the subarray sum prefix - p while staying within the bound.

Q: Can this be solved without a sorted set? A: Yes, with O(m²) per column pair (check all subarray sums directly), giving O(n² m²) overall — simpler but slower. The sorted set trades code complexity for a log factor speedup.

Q: What if no rectangle sums to exactly k? A: That's fine — the problem guarantees a rectangle with sum no larger than k exists; the algorithm naturally finds the closest sum from below.

Quick Revision​

  • Problem: find the maximum rectangle sum that does not exceed k.
  • Fix left and right column boundaries to reduce to a 1D problem.
  • Compress the matrix slice into a row-sum array between those columns.
  • Use prefix sums over the row-sum array to represent subarray sums.
  • Maintain a sorted set of prefix sums seen so far.
  • For each new prefix, binary search for the smallest prefix ≥ prefix - k.
  • That gives the max subarray sum ≤ k ending at the current position.
  • Track the global best across all column pairs.
  • Time: O(min(m,n)² · max(m,n) · log(max(m,n))); Space: O(m).
  • Iterate the smaller dimension outward for better performance.
  • 304 - Range Sum Query 2D - Immutable — same column-compression / prefix-sum-over-2D-matrix technique.
  • 307 - Range Sum Query - Mutable — related prefix-sum family for range queries.
  • Also related in pattern: "maximum subarray sum no larger than k" (1D version) — solved with prefix sums + sorted set/binary search, the core subroutine used here.