LeetCode 363: Max Sum of Rectangle No Larger Than K

i recently solved the max sum of rectangle no larger than k problem on leetcode, and it’s a great example of dynamic programming and 2d range queries. this hard problem tests your understanding of prefix sums, rectangle enumeration, and efficient constraint handling.

Problem Statement

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.

example 1:

input: matrix = [[1,0,1],[0,-2,3]], k = 2
output: 2

explanation: because the sum of 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

My Approach

when i first saw this problem, i immediately thought about using a 2d prefix sum approach. the key insight is building a prefix sum array to efficiently calculate rectangle sums and then enumerating all possible rectangles to find the maximum sum that satisfies the constraint.

Initial Thoughts

i started by thinking about different approaches:

2d prefix sum - build prefix sum for efficient range queries
brute force - try all possible rectangles
dynamic programming - use dp for optimal substructure
sliding window - use sliding window for 1d case

Solution Strategy

i decided to use a 2d prefix sum approach with the following strategy:

prefix sum construction - build 2d prefix sum array for efficient range queries
rectangle enumeration - try all possible rectangle sizes
sum calculation - use prefix sum to calculate rectangle sum in O(1)
constraint handling - ensure sum is no larger than k
maximum tracking - track the maximum sum that satisfies the constraint

My Solution

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var maxsumsubmatrix = function(matrix, k) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    // build 2d prefix sum
    const prefixsum = array(m + 1).fill().map(() => array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            prefixsum[i][j] = matrix[i-1][j-1] + 
                             prefixsum[i-1][j] + 
                             prefixsum[i][j-1] - 
                             prefixsum[i-1][j-1];
        }
    }
    
    let maxsum = -infinity;
    
    // try all possible rectangle sizes
    for (let top = 0; top < m; top++) {
        for (let bottom = top; bottom < m; bottom++) {
            for (let left = 0; left < n; left++) {
                for (let right = left; right < n; right++) {
                    const sum = prefixsum[bottom + 1][right + 1] - 
                               prefixsum[top][right + 1] - 
                               prefixsum[bottom + 1][left] + 
                               prefixsum[top][left];
                    
                    if (sum <= k) {
                        maxsum = math.max(maxsum, sum);
                    }
                }
            }
        }
    }
    
    return maxsum;
};

Code Breakdown

let me walk through how this solution works:

1. Prefix Sum Construction

const prefixsum = array(m + 1).fill().map(() => array(n + 1).fill(0));

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        prefixsum[i][j] = matrix[i-1][j-1] + 
                         prefixsum[i-1][j] + 
                         prefixsum[i][j-1] - 
                         prefixsum[i-1][j-1];
    }
}

we build the 2d prefix sum array:

initialization: create (m+1) x (n+1) array filled with zeros
inclusion-exclusion: use the principle to avoid double counting
formula: prefixsum[i][j] = matrix[i-1][j-1] + prefixsum[i-1][j] + prefixsum[i][j-1] - prefixsum[i-1][j-1]

2. Rectangle Enumeration

for (let top = 0; top < m; top++) {
    for (let bottom = top; bottom < m; bottom++) {
        for (let left = 0; left < n; left++) {
            for (let right = left; right < n; right++) {
                // calculate sum for this rectangle
            }
        }
    }
}

we enumerate all possible rectangles:

top: starting row (0 to m-1)
bottom: ending row (top to m-1)
left: starting column (0 to n-1)
right: ending column (left to n-1)

3. Sum Calculation

const sum = prefixsum[bottom + 1][right + 1] - 
           prefixsum[top][right + 1] - 
           prefixsum[bottom + 1][left] + 
           prefixsum[top][left];

we calculate rectangle sum using prefix sum:

inclusion-exclusion: subtract overlapping regions
formula: sum = prefixsum[bottom+1][right+1] - prefixsum[top][right+1] - prefixsum[bottom+1][left] + prefixsum[top][left]
efficiency: O(1) time complexity

4. Constraint Handling

if (sum <= k) {
    maxsum = math.max(maxsum, sum);
}

we check the constraint and update maximum:

constraint check: ensure sum ≤ k
maximum tracking: update maxsum if constraint is satisfied
initialization: start with -infinity

5. Prefix Sum Logic

// the key insight: inclusion-exclusion principle
// sum = bottom_right - top_right - bottom_left + top_left

the inclusion-exclusion principle:

bottom_right: includes the entire rectangle
top_right: subtracts the top portion
bottom_left: subtracts the left portion
top_left: adds back the double-subtracted corner

Example Walkthrough

let’s trace through the example: matrix = [[1,0,1],[0,-2,3]], k = 2

step 1: build prefix sum
original matrix:
[1, 0, 1]
[0, -2, 3]

prefix sum:
[0, 0, 0, 0]
[0, 1, 1, 2]
[0, 1, -1, 2]

step 2: try rectangles
rectangle (0,0,0,0): sum = 1 ≤ 2, maxsum = 1
rectangle (0,0,0,1): sum = 1 ≤ 2, maxsum = 1
rectangle (0,0,0,2): sum = 2 ≤ 2, maxsum = 2
rectangle (0,1,0,2): sum = 3 > 2, skip
rectangle (1,1,2,2): sum = 3 > 2, skip

result: 2

Time and Space Complexity

time complexity: O(m²n²) where m and n are matrix dimensions
space complexity: O(mn) for prefix sum array

the algorithm is efficient because:

prefix sum construction is O(mn)
rectangle enumeration is O(m²n²)
sum calculation is O(1) for each rectangle
space usage is optimal

Key Insights

2d prefix sum - efficient range queries in O(1)
inclusion-exclusion - handle overlapping regions correctly
rectangle enumeration - try all possible rectangles
constraint handling - ensure sum ≤ k

Alternative Approaches

i also considered:

brute force - calculate sum for each rectangle
- O(m²n²) time for sum calculation
- O(m²n²) total time complexity
- less efficient than prefix sum
dynamic programming - use dp for optimal substructure
- more complex implementation
- same time complexity
- harder to understand
sliding window - use sliding window for 1d case
- only works for 1d arrays
- not suitable for 2d matrices
- incorrect approach
binary search - search for optimal sum
- more complex implementation
- same time complexity
- unnecessary complexity

Edge Cases to Consider

empty matrix - handle edge case
single element - handle 1x1 matrix
all negative - handle negative sums
large k - handle large constraint values
small matrix - handle minimal input
zero matrix - handle all zeros

JavaScript-Specific Features

array methods - fill(), map() for efficient array creation
math functions - math.max() for maximum calculation
nested loops - efficient rectangle enumeration
arrow functions - concise function syntax
const declarations - immutable variables

Lessons Learned

this problem taught me:

2d prefix sums - efficient range queries in 2d
inclusion-exclusion - handle overlapping regions
rectangle enumeration - systematic approach to 2d problems
constraint optimization - find maximum under constraint

Real-World Applications

this problem has applications in:

image processing - region sum queries
computer vision - feature extraction
data analysis - 2d data aggregation
game development - collision detection

Conclusion

the max sum of rectangle no larger than k problem is an excellent exercise in 2d dynamic programming and range queries. the key insight is using 2d prefix sums for efficient rectangle sum calculation and systematically enumerating all possible rectangles.

you can find my complete solution on leetcode.

this is part of my leetcode problem-solving series. i’m documenting my solutions to help others learn and to track my own progress.