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.
It is guaranteed that there will be a rectangle with a sum no larger than k.
Examples:
Example 1:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
Example 2:
Input: matrix = [[2,2,-1]], k = 3
Output: 3Solution in Python
To solve the problem of finding the maximum sum of a rectangle within a 2D matrix such that the sum does not exceed a given integer k, we can break down the problem as follows:
Approach:
This problem is a variation of the maximum subarray sum problem, but extended to two dimensions (rectangles within a matrix). The challenge is not just finding the rectangle with the maximum sum, but ensuring that the sum is no larger than k.
Key Insights:
- Submatrix Sum Calculation: We need to efficiently calculate the sum of all possible submatrices. A brute-force approach that computes the sum of every possible rectangle would be too slow (O(m² * n²) for all submatrices).
- Kadane’s Algorithm: A well-known algorithm for solving the 1D maximum subarray problem can be adapted to help solve this problem. Kadane’s algorithm can be applied to each pair of rows, reducing the problem to 1D for each submatrix.
- Bounding the Sum with k: The tricky part is ensuring that the submatrix sum is less than or equal to
k. To achieve this efficiently, we can use a prefix sum and a sorted data structure (such as aSortedList) to find the sum of a subarray that is as close tokas possible without exceeding it.
Detailed Steps:
- Iterating over row pairs: Consider submatrices that span between pairs of rows. For each pair of rows, the problem is reduced to finding a subarray sum (in 1D) that does not exceed
k. - Using a prefix sum array: As we traverse each pair of rows, compute the prefix sum of the columns, and check if there’s a valid subarray whose sum is no larger than
k. - Binary search for valid subarrays: To find the subarray sum efficiently, maintain a sorted list of prefix sums, and use binary search to quickly find a prefix sum that satisfies the condition.
Python
class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
# Get the dimensions of the matrix
m, n = len(matrix), len(matrix[0])
# Initialize the result variable to a very small number
max_sum = float('-inf')
# Iterate over all pairs of row ranges (i to j)
for left in range(n):
# Initialize a 1D array to store the row sums between two columns
row_sums = [0] * m
for right in range(left, n):
# Update the row_sums array by adding elements from the current column (right)
for i in range(m):
row_sums[i] += matrix[i][right]
# Now we have a 1D problem: Find the maximum sum of any subarray in row_sums that is <= k
# We use a sorted list of prefix sums to do this efficiently
prefix_sums = [0]
current_sum = 0
for sum_value in row_sums:
# Update the current prefix sum
current_sum += sum_value
# We want to find the largest prefix sum such that (current_sum - prefix_sum) <= k
# Hence, we need to find the smallest prefix_sum >= current_sum - k
target = current_sum - k
idx = bisect_left(prefix_sums, target)
if idx < len(prefix_sums):
max_sum = max(max_sum, current_sum - prefix_sums[idx])
# Insert the current prefix_sum into the sorted list
insort(prefix_sums, current_sum)
return max_sumExplanation of the Code:
- Prefix Sums: The key idea is to use prefix sums to compute the sum of submatrices more efficiently. By summing up elements between two columns, we reduce the problem to a 1D array, and then use a sorted list of prefix sums to find the subarray with the maximum sum less than or equal to
k. - Outer Loops:
- The outer loop iterates over all possible pairs of columns (
leftandright). - For each column pair, we maintain an array
row_sums, where each element represents the sum of elements between theleftandrightcolumns for a specific row.
- The outer loop iterates over all possible pairs of columns (
- Prefix Sum and Binary Search:
- For each subarray (represented by
row_sums), we calculate the cumulative sum (i.e., prefix sum) as we iterate through the rows. - We use binary search (
bisect_left) to find the smallest prefix sum that allows the subarray sum to remain below or equal tok. - We keep track of the maximum valid subarray sum in
max_sum.
- For each subarray (represented by
- Handling Edge Cases:
- If the matrix has only one element or only one row/column, the algorithm will still work correctly due to the way it reduces the problem to 1D for each pair of columns.
Solution in C++
C++
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int rows = matrix.size(); // number of rows in the matrix
int cols = matrix[0].size(); // number of columns in the matrix
int maxSum = INT_MIN; // initialize maximum sum to smallest possible integer
// Iterate over all column pairs
for (int left = 0; left < cols; ++left) {
// Initialize an array to store the sum of elements in each row between two column pairs
vector<int> rowSum(rows, 0);
// Extend the right boundary of the rectangle
for (int right = left; right < cols; ++right) {
// Update rowSum to include the elements from the new right column
for (int i = 0; i < rows; ++i) {
rowSum[i] += matrix[i][right];
}
// Now find the maximum subarray sum no larger than k for this rowSum array
maxSum = max(maxSum, findMaxSubarraySum(rowSum, k));
}
}
return maxSum;
}
private:
// Helper function to find the maximum subarray sum no larger than k
int findMaxSubarraySum(vector<int>& arr, int k) {
int currentSum = 0;
int maxSum = INT_MIN;
// Use a set to store the prefix sums
set<int> prefixSums;
prefixSums.insert(0); // Add 0 as the initial prefix sum for comparison
for (int sum : arr) {
currentSum += sum;
// Find the smallest prefix sum >= currentSum - k
auto it = prefixSums.lower_bound(currentSum - k);
if (it != prefixSums.end()) {
// Update maxSum if a valid subarray sum is found
maxSum = max(maxSum, currentSum - *it);
}
// Insert the current prefix sum into the set
prefixSums.insert(currentSum);
}
return maxSum;
}
};Solution in Javascript
JavaScript
var maxSumSubmatrix = function(matrix, k) {
// Function to find the maximum sum subarray in a 1D array that is no larger than k
const maxSumNoLargerThanK = (arr, k) => {
let maxSum = -Infinity;
let currSum = 0;
let sumSet = [0]; // Stores prefix sums
for (let sum of arr) {
currSum += sum;
// Find the smallest prefix sum such that currSum - prefix <= k
let left = binarySearch(sumSet, currSum - k);
if (left !== null) {
maxSum = Math.max(maxSum, currSum - sumSet[left]);
}
// Insert current prefix sum in sorted order
insertInOrder(sumSet, currSum);
}
return maxSum;
};
// Binary search to find the first element greater than or equal to the target
const binarySearch = (arr, target) => {
let left = 0, right = arr.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] >= target) right = mid;
else left = mid + 1;
}
return left < arr.length ? left : null;
};
// Insert element into sorted array
const insertInOrder = (arr, num) => {
let left = 0, right = arr.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] < num) left = mid + 1;
else right = mid;
}
arr.splice(left, 0, num);
};
let maxResult = -Infinity;
let rows = matrix.length, cols = matrix[0].length;
// Iterate through all pairs of rows
for (let leftRow = 0; leftRow < rows; leftRow++) {
let rowSum = new Array(cols).fill(0); // Array to store the sum of elements between the two rows
for (let rightRow = leftRow; rightRow < rows; rightRow++) {
// Update the sum for each column within the row range
for (let col = 0; col < cols; col++) {
rowSum[col] += matrix[rightRow][col];
}
// Find the max subarray sum within the column range that is no larger than k
maxResult = Math.max(maxResult, maxSumNoLargerThanK(rowSum, k));
}
}
return maxResult;
};Solution in Java
Java
class Solution {
// Method to find the maximum sum of a submatrix no larger than k
public int maxSumSubmatrix(int[][] matrix, int k) {
// Initialize variables
int rows = matrix.length; // Number of rows in the matrix
int cols = matrix[0].length; // Number of columns in the matrix
int maxSum = Integer.MIN_VALUE; // To keep track of the maximum sum <= k
// Loop over each pair of columns to define the boundaries of the rectangle
for (int left = 0; left < cols; left++) {
// Create an array to store the row sums between the left and right boundaries
int[] rowSums = new int[rows];
// Move the right boundary from the left to the end of the matrix
for (int right = left; right < cols; right++) {
// Update the rowSums array by adding the values between the left and right boundaries
for (int row = 0; row < rows; row++) {
rowSums[row] += matrix[row][right];
}
// Now find the maximum sum of a subarray in rowSums that is <= k
maxSum = Math.max(maxSum, findMaxSumNoLargerThanK(rowSums, k));
}
}
return maxSum; // Return the maximum sum found
}
// Helper method to find the maximum sum of a subarray in rowSums no larger than k
private int findMaxSumNoLargerThanK(int[] arr, int k) {
// Use a TreeSet to help find the prefix sums and their differences
TreeSet<Integer> prefixSums = new TreeSet<>();
prefixSums.add(0); // Add 0 to the TreeSet to handle subarrays starting from index 0
int currentSum = 0; // To track the cumulative sum
int maxSum = Integer.MIN_VALUE; // To track the maximum sum <= k
for (int num : arr) {
// Update the current cumulative sum
currentSum += num;
// We need to find a prefix sum such that currentSum - prefixSum <= k
// This means prefixSum >= currentSum - k
Integer target = prefixSums.ceiling(currentSum - k);
// If such a prefix sum exists, update the maxSum
if (target != null) {
maxSum = Math.max(maxSum, currentSum - target);
}
// Add the current cumulative sum to the TreeSet
prefixSums.add(currentSum);
}
return maxSum; // Return the maximum sum found for this subarray
}
}