🌱 Keegan's Digital Garden

363. Max Sum of Rectangle No Larger Than K

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- brute force: iterate over all possible subarrays (quadratic in time complexity)

💡 Explanation of Solution

  1. Iterate Over All Possible Row Pairs:
    • We iterate over all possible pairs of row indices (r1, r2). The goal is to collapse the 2D matrix into a 1D array (column-wise sums) for each pair of rows.
    • This reduces the problem to finding the maximum sum subarray in a 1D array that does not exceed k.
  2. Convert the 2D Problem into a 1D Subarray Problem:
    • For each row range (r1, r2), we compute the cumulative sum for each column into a colSums array.
    • Then, we need to find the maximum sum subarray in colSums that is ≤ k.
  3. Use a Sorted Data Structure (set<int>) for Efficient Subarray Sum Computation:
    • To find the maximum subarray sum that is ≤ k, we maintain a prefix sum set.
    • We iterate through colSums, maintaining a running prefix sum.
    • At each step, we use lower_bound in the sorted set to find the smallest prefix sum such that (prefixSum - prevPrefix) <= k.
  4. Update the Maximum Sum:
    • For each (r1, r2), update the global maximum sum found.

Observations:

  • Binary Search via set<int>:
    • We use std::set<int> to efficiently find a prefix sum prevPrefix such that prefixSum - prevPrefix ≤ k, using lower_bound().
  • Prefix Sum Technique:
    • This allows us to efficiently check subarrays without having to recompute all possible subarrays explicitly.
  • Collapsing Rows into a 1D Array:
    • Reduces the problem complexity significantly compared to a brute-force O(m² * n²) approach.

⌛ Complexity Analysis

  • Fix Two Rows (r1, r2): O(m²)
  • Compute colSums: O(n)
  • Find Max Subarray Sum Using set<int>: O(n log n) (since lower_bound is O(log n))
  • Total Complexity: O(m² * n log n)

💻 Implementation of Solution

/*
    input:
        - m*n matrix
        - int k
    
    return: max sum of a rectangle in the matrix
    that its sum is <= than k
 
    it is guaranteed that there will be a rectangle with a sum no larger than k
*/
 
class Solution {
public:
int maxSumSubarrayNoMoreThanK(vector<int>& arr, int k) {
    set<int> prefixSums;
    prefixSums.insert(0);
    int maxSum = INT_MIN, prefixSum = 0;
 
    for (int sum : arr) {
        prefixSum += sum;
 
        // Find the smallest prefix sum where (prefixSum - prevPrefix) <= k
        auto it = prefixSums.lower_bound(prefixSum - k);
        if (it != prefixSums.end()) {
            maxSum = max(maxSum, prefixSum - *it);
        }
 
        // Insert the current prefix sum into the set
        prefixSums.insert(prefixSum);
    }
    return maxSum;
}
 
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
    int rows = matrix.size(), cols = matrix[0].size();
    int maxSum = INT_MIN;
 
    // Fix row1 and row2 to collapse into a 1D column sum array
    for (int r1 = 0; r1 < rows; r1++) {
        vector<int> colSums(cols, 0);
 
        for (int r2 = r1; r2 < rows; r2++) {
            // Update colSums by adding values from row r2
            for (int c = 0; c < cols; c++) {
                colSums[c] += matrix[r2][c];
            }
 
            // Find the max subarray sum for colSums that does not exceed k
            int currMax = maxSumSubarrayNoMoreThanK(colSums, k);
            maxSum = max(maxSum, currMax);
        }
    }
    return maxSum;
}
};

Graph View