Max sum of rectangle no larger than k

Array Binary Search Matrix Prefix Sum Ordered Set

45.3% acceptance

Jan 12, 2026

3569

178

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeSet;

impl Solution {
  pub fn max_sum_submatrix(matrix: Vec<Vec<i32>>, k: i32) -> i32 {
    let m = matrix.len();
    let n = matrix[0].len();
    let mut result = i32::MIN;
    
    for left in 0..n {
      let mut row_sum = vec![0; m];
      
      for right in left..n {
        for i in 0..m {
          row_sum[i] += matrix[i][right];
        }
        
        // Find max subarray sum <= k
        let mut set = BTreeSet::new();
        set.insert(0);
        let mut cur_sum = 0;
        
        for &sum in &row_sum {
          cur_sum += sum;
          if let Some(&val) = set.range(cur_sum - k..).next() {
            result = result.max(cur_sum - val);
          }
          set.insert(cur_sum);
        }
      }
    }
    
    result
  }
}