Vultr DocsLatest Content

Max Sum of Rectangle No Larger Than K

Updated on 12 June, 2025
Max Sum of Rectangle No Larger Than K header image

Problem Statement

Given a matrix matrix of dimensions m x n and an integer k, the task is to identify the maximum sum of any rectangle within this matrix where the sum does not exceed k. The rectangle can be of any size, ranging from a single element to covering the entire matrix. The guarantee that a rectangle's sum no larger than k exists simplifies our task to not just finding a valid rectangle, but locating one with the maximal sum under the given constraint.

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:

3

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -100 <= matrix[i][j] <= 100
  • -105 <= k <= 105

Approach and Intuition

  1. Brute-force Exploration: Given the constraints, a potential approach might involve iterating over all possible rectangles within the matrix. This involves:

    • Choosing two rows and within those rows, iterating over all possible pairs of columns to define the corners of the rectangle.
    • For each rectangle, compute the sum and check if it's the largest encountered that also doesn't exceed k.

  2. Efficient Computation Using Prefix Sums:

    • Use a two-dimensional prefix sum array to quickly compute the sum of any sub-rectangle. This significantly lowers the operational complexity from potentially recalculating sums from scratch each time.

  3. Optimized Search with Data Structures:

    • Once you have a way to calculate rectangle sums quickly, use advanced data structures like balanced trees or arrays in conjunction with algorithms like binary search to manage and compare these sums more efficiently.

  4. Applicability of Kadane’s Algorithm for 2D:

    • Just like Kadane’s Algorithm finds the maximum sum subarray in a 1D array, we can modify it to work for 2D arrays by fixing two rows at a time and reducing the problem to a 1D max subarray sum for these bounds.

  5. Handling Constraints and Edge Cases:

    • Ensure the solution is robust to handle the lowest and highest possible values in the matrices and k, considering negative numbers, especially given the range of matrix element values from -100 to 100 and k from -105 to 105.

Intuition: The challenge resembles finding a needle in a haystack, but instead of randomly searching, we methodically reduce our search space using math (prefix sums), data structures for quick access and comparisons, and algorithms that transform a complex problem into a simpler one. The expectation is not just to find a sum below k, but to maximize it under the given constraint. Hence, combining efficiency in search with effective sum calculation becomes the cornerstone of our approach.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int optimalResult = INT_MIN;

    int calculateKadane(vector<int>& data) {
        int maxKadane = INT_MIN, currentMax = 0;
        for (int& value : data) {
            currentMax = max(currentMax + value, value);
            maxKadane = max(maxKadane, currentMax);
        }
        return maxKadane;
    }
    void evaluateMax(vector<int>& data, int k) {
        int kadaneResult = calculateKadane(data);

        if (kadaneResult <= k) {
            optimalResult = max(optimalResult, kadaneResult);
            return;
        }
        
        int accumulatedSum = 0;
        set<int> prefixSums;
        set<int>::iterator iter;

        prefixSums.insert(0);
        for (int& value : data) {
            accumulatedSum += value;
            iter = prefixSums.lower_bound(accumulatedSum - k);

            if (iter != prefixSums.end())
                optimalResult = max(optimalResult, accumulatedSum - *iter);

            prefixSums.insert(accumulatedSum);
        }
    }
    int maximumSumSubmatrix(vector<vector<int>>& matrix, int k) {
        if (matrix[0].size() > matrix.size()) {
            vector<int> cumulativeRowSum(matrix[0].size());
            for (int i = 0; i < matrix.size(); i++) {
                fill(cumulativeRowSum.begin(), cumulativeRowSum.end(), 0);
                for (int row = i; row < matrix.size(); row++) {
                    for (int col = 0; col < matrix[0].size(); col++)
                        cumulativeRowSum[col] += matrix[row][col];
                    
                    evaluateMax(cumulativeRowSum, k);

                    if (optimalResult == k) return optimalResult;
                }
            }
        } else {
            vector<int> cumulativeColSum(matrix.size());
            for (int i = 0; i < matrix[0].size(); i++) {
                fill(cumulativeColSum.begin(), cumulativeColSum.end(), 0);
                for (int col = i; col < matrix[0].size(); col++) {
                    for (int row = 0; row < matrix.size(); row++)
                        cumulativeColSum[row] += matrix[row][col];

                    evaluateMax(cumulativeColSum, k);

                    if (optimalResult == k) return optimalResult;
                }
            }
        }
        return optimalResult;
    }
};

This C++ solution addresses the problem of finding the maximum sum of a rectangular area in a matrix, where the sum does not exceed a given threshold value k. The solution employs the Kadane's algorithm tailored to handle a 2D matrix and complemented with a set for prefix sums to efficiently track and compute required sums close to k.

  • The Solution class maintains a member optimalResult initialized to the smallest integer to keep track of the maximum subarray sum found.
  • calculateKadane function: Applies Kadane's algorithm to a 1D vector to find the maximum subarray sum.
  • evaluateMax function: Uses the result from Kadane's algorithm directly if it is within the bounds of k. If not, it employs a prefix sum approach utilizing a set to determine the optimal sum that does not exceed k.
  • maximumSumSubmatrix function: Handles the main logic of expanding the application of Kadane's algorithm from 1D to 2D. Depending on the matrix dimensions, it opts to compress the matrix either by columns or rows. This process involves:
    • Creating a cumulative sum for rows or columns.
    • Applying evaluateMax to determine the optimal subarray sum for each row or column compression.
    • Checking if the current optimalResult matches k, enabling an early exit for efficiency.

Implementing such a solution ensures that the rectangular subarray with the maximum possible sum under the constraint of k is determined efficiently. This is particularly effective due to the combination of dynamic programming (Kadane’s algorithm) and efficient set operations for prefix sums, making it suitable for larger matrices where brute-force methods would be too slow.

java 
class Solution {
    int globalMax = Integer.MIN_VALUE;

    int findMaxSubArraySum(int[] data) {
        int temporaryMax = Integer.MIN_VALUE, currentSum = 0;
        for (int value : data) {
            currentSum = Math.max(currentSum + value, value);
            temporaryMax = Math.max(temporaryMax, currentSum);
        }
        return temporaryMax;
    }

    void checkAndUpdateResult(int[] elements, int threshold) {
        int maxSubArraySum = findMaxSubArraySum(elements);
        if (maxSubArraySum <= threshold) {
            globalMax = Math.max(globalMax, maxSubArraySum);
            return;
        }
        int accumulatedSum = 0;
        TreeSet<Integer> prefixSumSet = new TreeSet<>();
        prefixSumSet.add(0);
        for (int element : elements) {
            accumulatedSum += element;
            Integer minimalPrefix = prefixSumSet.ceiling(accumulatedSum - threshold);
            if (minimalPrefix != null)
                globalMax = Math.max(globalMax, accumulatedSum - minimalPrefix);
            prefixSumSet.add(accumulatedSum);
        }
    }

    public int maximumSumRectangle(int[][] grid, int threshold) {
        if (grid[0].length > grid.length) {
            int[] cumulativeRows = new int[grid[0].length];
            for (int startRow = 0; startRow < grid.length; startRow++) {
                Arrays.fill(cumulativeRows, 0);
                for (int row = startRow; row < grid.length; row++) {
                    for (int column = 0; column < grid[0].length; column++)
                        cumulativeRows[column] += grid[row][column];
                    checkAndUpdateResult(cumulativeRows, threshold);
                    if (globalMax == threshold)
                        return globalMax;
                }
            }
        } else {
            int[] cumulativeColumns = new int[grid.length];
            for (int startColumn = 0; startColumn < grid[0].length; startColumn++) {
                Arrays.fill(cumulativeColumns, 0);
                for (int col = startColumn; col < grid[0].length; col++) {
                    for (int row = 0; row < grid.length; row++)
                        cumulativeColumns[row] += grid[row][col];
                    checkAndUpdateResult(cumulativeColumns, threshold);
                    if (globalMax == threshold)
                        return globalMax;
                }
            }
        }
        return globalMax;
    }
}

The Java solution for the problem "Max Sum of Rectangle No Larger Than K" optimizes finding the maximum sum of a subrectangle in a given matrix where the sum does not exceed a specified threshold. Here’s how the solution works:

  • Initialization: A globalMax variable is used to track the highest sum found that satisfies the condition defined by threshold.

  • Key Functions:

    1. findMaxSubArraySum: This function calculates the maximum sum of a contiguous subarray using Kadane's algorithm. It returns the maximum subarray sum for an array of integers.

    2. checkAndUpdateResult: Given an array of elements and a threshold, this function uses the result from findMaxSubArraySum. If the result is within the threshold, it updates the globalMax. If it's not, the function then uses a TreeSet to find subarrays within the threshold more precisely and updates globalMax accordingly.

  • Logic for Processing the Matrix:

    • The method changes the approach based on whether the grid's width is greater than its height. It ensures optimizing space and time by transforming the 2D matrix summation problem to multiple 1D maximum subarray problems, either by rows or by columns.

    • Within the nested loops, the matrix is traversed and cumulative sum arrays (cumulativeRows or cumulativeColumns) are updated and evaluated by checkAndUpdateResult.

    • The solution immediately returns globalMax if its value matches exactly with the threshold during iterations, optimizing performance by stopping further unnecessary calculations.

This method optimally handles the matrix dimensions by processing as per the smaller dimension, either row-wise or column-wise which makes it efficient for different sizes of input matrices. Also, using the TreeSet for precise control on the subarray sums relating to the threshold provides a significant boost by reducing potential computation overheads. The algorithm efficiently narrows down areas of interest in the matrix using row or column cumulations and further processes them to find the maximum possible subarray sum within the given constraints.

Comments

No comments yet.