LeetCode Solutions Blog

Max Sum of Rectangle No Larger Than K

Number: 363

Difficulty: Hard

Paid? No

Problem Description

Given an m x n matrix and an integer k, find the maximum sum of any rectangle in the matrix such that the sum is no larger than k. It is guaranteed that such a rectangle exists.

Key Insights

Reducing the 2D problem to multiple 1D problems by fixing column boundaries.
For each fixed pair of columns, compute the row-wise cumulative sums to form a 1D array.
Use a prefix sum combined with binary search (or an ordered set) to find the maximum subarray sum no larger than k in the 1D array.
The challenge arises from efficiently finding a subarray sum constraint by k, which requires careful use of data structures.

Space and Time Complexity

Time Complexity: O(min(m, n)^2 * max(m, n) * log(max(m, n)))
Space Complexity: O(max(m, n))

Solution

The solution iterates over all pairs of columns (or rows, depending on the matrix dimension) to compress the matrix into a 1D array representing the sum of elements between the two fixed columns for each row. Then, for each 1D array, we use prefix sums and binary search to determine the greatest sum that does not exceed k. A balanced tree (or an ordered set) is used to store prefix sums, along with binary search methods to quickly query the smallest prefix sum that meets the required criteria (currentPrefix - candidate >= k). Special attention is needed to handle negative numbers and to ensure the search can correctly identify edge cases.

Code Solutions

# Python solution using the sorted list from the bisect module
import bisect

def maxSumSubmatrix(matrix, k):
    # If rows are larger than columns, transpose the matrix for efficiency.
    if len(matrix) > len(matrix[0]):
        matrix = list(zip(*matrix))
    
    result = float('-inf')
    rows, cols = len(matrix), len(matrix[0])
    
    # Iterate over all pairs of left and right columns
    for left in range(cols):
        rowSums = [0] * rows
        for right in range(left, cols):
            # Update the row sums for the rectangle defined by left and right
            for i in range(rows):
                rowSums[i] += matrix[i][right]
            
            # Find the max subarray no larger than k using prefix sum and binary search.
            prefixSums = [0]
            currentSum = 0
            for sum_val in rowSums:
                currentSum += sum_val
                # We want: currentSum - prev >= -k  ===> prev <= currentSum - k
                target = currentSum - k
                # Locate the leftmost index where prefixSums[idx] >= target
                idx = bisect.bisect_left(prefixSums, target)
                if idx < len(prefixSums):
                    candidate = currentSum - prefixSums[idx]
                    if candidate == k:
                        return k
                    result = max(result, candidate)
                # Insert currentSum maintaining sorted order.
                bisect.insort(prefixSums, currentSum)
    return result

# Example usage:
matrix = [[1,0,1],[0,-2,3]]
k = 2
print(maxSumSubmatrix(matrix, k))  # Output should be 2