Max Sum of Rectangle No Larger Than K - Practice Coding Problems

Max Sum of Rectangle No Larger Than K - Problem

Array Binary Search Matrix Prefix Sum Ordered Set Hard

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.

A rectangle is defined by its top-left corner and bottom-right corner.

Input & Output

Example 1 — Basic Case

$ Input: matrix = [[1,0,1],[0,-2,3]], k = 2

› Output: 2

💡 Note: The rectangle with corners (0,0) to (0,2) has sum = 1 + 0 + 1 = 2, which equals k

Example 2 — Single Cell

$ Input: matrix = [[2,2,-1]], k = 3

› Output: 3

💡 Note: The rectangle from (0,0) to (0,1) has sum = 2 + 2 = 4 > k, so we take single cell 2 or rectangle [2,-1] with sum 1, but [2,2] without -1 isn't valid. Best is single cell with value 2.

Example 3 — Negative Values

$ Input: matrix = [[-1,2],[-1,3]], k = 0

› Output: 0

💡 Note: Rectangle from (0,1) to (1,0) would be invalid. Single cells: -1,-1,2,3. Rectangles: [-1,2]=1, [-1,3]=2, [2,3]=5, [-1,-1]=-2, full=3. Only -1 ≤ 0, and -2 ≤ 0. Best is -1.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 100
-100 ≤ matrix[i][j] ≤ 100
-10⁵ ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Matrix Input

2D matrix with positive and negative values

Find Rectangles

Search all possible rectangular regions

Maximum Valid Sum

Return largest sum that doesn't exceed k

Key Takeaway

🎯 Key Insight: Convert 2D rectangle problem to multiple 1D maximum subarray problems using row compression

Asked in

G Google 45 M Microsoft 35 a Amazon 30 f Facebook 25

The key insight is reducing the 2D rectangle problem to multiple 1D maximum subarray problems. Fix top/bottom rows, compress columns, then use Kadane's algorithm with binary search on prefix sums. Best approach achieves O(m²n log n) time, O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Kadane + Binary Search	O(m²n log n)	O(n)	Reduce to 1D subarray problem with binary search optimization
Brute Force - All Rectangles	O(m²n²(m+n))	O(1)	Check every possible rectangle and find maximum sum ≤ k
Prefix Sum Optimization	O(m²n²)	O(mn)	Use prefix sums to calculate rectangle sums in O(1)

Kadane + Binary Search — Algorithm Steps

Step 1: Fix top and bottom rows, compress columns into 1D array
Step 2: For each 1D array, find maximum subarray sum ≤ k
Step 3: Use prefix sums with binary search to efficiently find valid subarrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix Rows

Fix top and bottom boundaries

Compress Columns

Sum columns to create 1D array

1D Subarray

Find max subarray ≤ k using binary search

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** matrix, int matrixSize, int* matrixColSize, int k) {
    int m = matrixSize, n = matrixColSize[0];
    int maxSum = INT_MIN;
    
    // Fix top and bottom rows
    for (int top = 0; top < m; top++) {
        int* colSums = (int*)calloc(n, sizeof(int));
        
        for (int bottom = top; bottom < m; bottom++) {
            // Add current bottom row to column sums
            for (int j = 0; j < n; j++) {
                colSums[j] += matrix[bottom][j];
            }
            
            // Solve 1D problem using simple approach
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = i; j < n; j++) {
                    sum += colSums[j];
                    if (sum <= k) {
                        if (sum > maxSum) {
                            maxSum = sum;
                        }
                    }
                }
            }
        }
        
        free(colSums);
    }
    
    return maxSum;
}

int main() {
    int matrix[100][100];
    int m = 2, n = 3;
    int k;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    scanf("%d", &k);
    
    int* matrixPtrs[100];
    int colSizes[100];
    for (int i = 0; i < m; i++) {
        matrixPtrs[i] = matrix[i];
        colSizes[i] = n;
    }
    
    int result = solution(matrixPtrs, m, colSizes, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n log n)

m² pairs of rows, for each pair process n columns with log n binary search

⚡ Linearithmic

Space Complexity

O(n)

1D array for column compression and set for prefix sums

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Kadane + Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler