We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Max Sum of Rectangle No Larger Than K

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem involves finding a sub-matrix (rectangle) whose sum does not exceed a given value k.
  • We can utilize prefix sums to efficiently calculate the sum of any sub-matrix.
  • A sliding window or 1D representation of the problem can be used to manage the sums dynamically.
  • We can employ a binary search approach combined with a data structure to keep track of the sums encountered so far.

Space and Time Complexity

Time Complexity: O(n^2 * log(m)), where n is the number of columns and m is the number of rows in the matrix. Space Complexity: O(m), for storing intermediate sums and results.

Solution

To solve this problem, we can iterate through pairs of rows in the matrix. For each pair of rows, we compress the 2D problem into a 1D problem by calculating the sum of each column between the two rows. This results in a temporary array representing the sum of elements for each column in the defined row range.

Next, we need to find the maximum sum of a subarray (or contiguous sequence) from this temporary array that does not exceed k. To achieve this efficiently, we can use a sorted data structure (like a balanced BST or ordered set) to keep track of the prefix sums we encounter while iterating through the temporary array. By searching for the closest prefix sum that, when subtracted from the current prefix sum, keeps the total sum under k, we can efficiently find valid rectangles and their sums.

Code Solutions

def maxSumSubmatrix(matrix, k):
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    max_sum = float('-inf')

    for left in range(cols):
        # Initialize a list to store the row sums
        row_sums = [0] * rows
        for right in range(left, cols):
            # Update the row sums for the current right boundary
            for row in range(rows):
                row_sums[row] += matrix[row][right]
            
            # Use a set to track prefix sums
            prefix_sums = {0}
            current_sum = 0
            for sum_value in row_sums:
                current_sum += sum_value
                # We need to find the largest prefix sum <= current_sum - k
                target = current_sum - k
                # Check if we can find a valid prefix sum using binary search
                for ps in sorted(prefix_sums):
                    if ps <= target:
                        max_sum = max(max_sum, current_sum - ps)
                    else:
                        break
                # Add current prefix sum to the set
                prefix_sums.add(current_sum)

    return max_sum
← Back to All Questions