363. Max Sum of Rectangle No Larger Than K

Q: Is Max Sum of Rectangle No Larger Than K easy or hard?

Max Sum of Rectangle No Larger Than K is classified as a Hard problem. It combines multiple concepts including 2D prefix sums, subarray optimization, and ordered sets, and requires reducing a matrix problem to repeated 1D searches.

Q: Max Sum of Rectangle No Larger Than K Python or Java solution?

Python implementations typically use the bisect module with a sorted list to simulate an ordered set, while Java solutions commonly use TreeSet. Both maintain sorted prefix sums so binary search can find valid subarray sums in O(log n) time.

Q: How to solve Max Sum of Rectangle No Larger Than K efficiently?

Convert the 2D rectangle problem into multiple 1D subarray problems. For every pair of columns, compute cumulative row sums and maintain prefix sums in a sorted structure. Use binary search to find the smallest prefix ≥ currentSum - k, which gives the best valid subarray ending at the current position.

Q: What is the best approach for Max Sum of Rectangle No Larger Than K?

The most efficient approach uses prefix sums combined with an ordered set (such as a balanced BST). Fix two column boundaries, compress the rows into a 1D array, and then find the maximum subarray sum ≤ k using prefix sums and binary search. This reduces the problem to O(cols^2 * rows log rows) time and O(rows) space.

Q: What data structure is used in Max Sum of Rectangle No Larger Than K?

The optimal solution uses an ordered set or balanced binary search tree to maintain prefix sums in sorted order. This structure enables efficient binary search to find the smallest prefix greater than or equal to currentSum - k while scanning the compressed array.

Q: What is the time complexity of Max Sum of Rectangle No Larger Than K?

The optimal solution runs in O(cols^2 * rows log rows). Two columns are fixed to define the rectangle width, rows are compressed into a 1D array, and an ordered set is used to search prefix sums in O(log rows). Brute-force prefix-sum approaches can take O(m^2 * n^2).

Q: Is Max Sum of Rectangle No Larger Than K asked at Google, Amazon, or Meta?

Max Sum of Rectangle No Larger Than K is a well-known hard matrix problem frequently associated with Google-style interviews. It tests prefix sums, binary search, and advanced data structures like ordered sets, which are common in high-level algorithm interviews.

The problem

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 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
-10⁵ <= k <= 10⁵

Follow up: What if the number of rows is much larger than the number of columns?

Approach overview

Problem Overview: You are given a 2D matrix and an integer k. The task is to find the maximum possible sum of any rectangular submatrix such that the sum does not exceed k. The challenge comes from efficiently exploring all rectangle combinations without exceeding time limits.

Approach 1: Prefix Sum with Iteration (Brute Force Optimization) (O(m^2 * n^2) time, O(1) extra space)

Compute a prefix sum matrix so you can calculate any rectangle sum in constant time. Iterate over every possible pair of top-left and bottom-right coordinates. For each pair, compute the rectangle sum using the prefix matrix and track the largest value that does not exceed k. This removes repeated summations but still checks all rectangles, leading to quadratic choices for rows and columns.

Approach 2: Prefix Sum + Ordered Set with Binary Search (Optimal) (O(cols^2 * rows log rows) time, O(rows) space)

Fix two column boundaries and compress the rows between them into a 1D array of cumulative sums. The problem then becomes: find the maximum subarray sum no larger than k. Maintain prefix sums and store them in an ordered structure (like a balanced BST or TreeSet). For each running prefix sum s, search for the smallest prefix ≥ s - k using binary search. This guarantees the largest valid subarray sum ending at the current row. Repeat for every column pair. The ordered structure is the key insight that avoids checking every subarray.

Approach 3: Recursive Approach with Memoization (O(m * n * states) time, O(m * n) space)

A recursive formulation explores rectangle boundaries while caching intermediate sums using memoization. Each recursive call expands a rectangle by adjusting row or column limits and stores previously computed sums to avoid recomputation. While memoization reduces duplicate work, the state space still grows quickly for large matrices. This approach is mainly useful for conceptual understanding or smaller constraints rather than optimal performance.

Recommended for interviews: The prefix-sum + ordered set solution is the expected answer. Interviewers want to see how you reduce the 2D rectangle problem into a 1D subarray constraint and then solve it using prefix sums and an ordered set. Explaining the brute force prefix-sum approach first shows problem decomposition, while the ordered-set optimization demonstrates strong algorithmic thinking.

Approach 1: Prefix Sum with Iteration

This approach involves calculating the prefix sum for every column and iterating over pairs of row indices to form vertical strips. The idea is derived from simplifying the multidimensional problem to a manageable form by transforming it into a 1D problem with the help of prefix sums and leveraging subarray sum computation techniques.

Python

import bisect

def maxSumSubmatrix(matrix, k):
    if not matrix or not matrix[0]: return 0
    max_sum = float('-inf')
    rows, cols = len(matrix), len(matrix[0])

    for left in range(cols):
        row_sum = [0] * rows
        for right in range(left, cols):
            for r in range(rows):
                row_sum[r] += matrix[r][right]
            max_sum = max(max_sum, maxSumNoLargerThanK(row_sum, k))

    return max_sum


def maxSumNoLargerThanK(nums, k):
    accu_sum, max_sum = 0, float('-inf')
    accu_sums = [0]
    for num in nums:
        accu_sum += num
        i = bisect.bisect_left(accu_sums, accu_sum - k)
        if i < len(accu_sums):
            max_sum = max(max_sum, accu_sum - accu_sums[i])
        bisect.insort(accu_sums, accu_sum)
    return max_sum

C++

#include <vector>
#include <set>

using namespace std;

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
    if (matrix.empty()) return 0;
    int maxSum = INT_MIN, rows = matrix.size(), cols = matrix[0].size();

    for (int left = 0; left < cols; ++left) {
        vector<int> rowSum(rows, 0);
        for (int right = left; right < cols; ++right) {
            for (int r = 0; r < rows; ++r) {
                rowSum[r] += matrix[r][right];
            }
            maxSum = max(maxSum, maxSumNoLargerThanK(rowSum, k));
        }
    }
    return maxSum;
}

int maxSumNoLargerThanK(vector<int>& nums, int k) {
    set<int> accuSet;
    accuSet.insert(0);
    int sum = 0, maxSum = INT_MIN;
    for (int num : nums) {
        sum += num;
        auto it = accuSet.lower_bound(sum - k);
        if (it != accuSet.end()) maxSum = max(maxSum, sum - *it);
        accuSet.insert(sum);
    }
    return maxSum;
}

The Python implementation uses a 2D prefix sum to convert the problem into finding a subarray sum no larger than k. We iterate over left and right column boundaries and compute row-wise sums in between. Then maxSumNoLargerThanK finds the maximum subarray sum no larger than k in these running row sums using a binary search approach (with the help of Python's bisect library) to maintain the cumulative sum.

Complexity

Time Complexity: O(n^2 * m log m), where m = num of rows and n = num of columns. Space Complexity: O(m) for storing row sums.

Try this approach in the editor

Approach 2: Recursive Approach with Memoization

This approach uses recursion to solve the problem by breaking it down into smaller subproblems and storing the results of these subproblems to avoid redundant calculations. Hence, it combines recursion with memoization.

Python

def fib(n, memo=None):
    if memo is None:
        memo = [-1] * (n + 1)
    if n <= 1:
        return n
    if memo[n] != -1:
        return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

n = 10  # Example
print(fib(n))

Java

import java.util.Arrays;

public class Solution {
    private static int[] memo;

    public static int fib(int n) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];
        memo[n] = fib(n-1) + fib(n-2);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10; // Example
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        System.out.println(fib(n));
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

int fib(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}

int main() {
    int n = 10; // Example
    vector<int> memo(n + 1, -1);
    cout << fib(n, memo) << endl;
    return 0;
}

JavaScript

function fib(n, memo = []) {
    if (n <= 1) return n;
    if (memo[n] !== undefined) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

let n = 10; // Example
console.log(fib(n));

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

#define MAX_SIZE 1000

int memo[MAX_SIZE];

int solve(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = solve(n-1) + solve(n-2);
}

int main() {
    memset(memo, -1, sizeof(memo));
    int n = 10; // Example
    printf("%d\n", solve(n));
    return 0;
}

using System;

class Program {
    static int[] memo;

    static int Fib(int n) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];
        memo[n] = Fib(n-1) + Fib(n-2);
        return memo[n];
    }

    static void Main() {
        int n = 10; // Example
        memo = new int[n + 1];
        for (int i = 0; i <= n; i++) memo[i] = -1;
        Console.WriteLine(Fib(n));
    }
}

The Python solution uses a list to store previously computed values and recursively calculates results as needed.

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor

Approach 3: Iterative Approach

This approach solves the problem iteratively, preventing the overhead of recursive function calls. It constructs a solution bottom-up and is generally more space-efficient.

Python

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

n = 10  # Example
print(fib(n))

Java

public class Solution {
    public static int fib(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1, c;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }

    public static void main(String[] args) {
        int n = 10; // Example
        System.out.println(fib(n));
    }
}

C++

#include <iostream>

using namespace std;

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 10; // Example
    cout << fib(n) << endl;
    return 0;
}

JavaScript

function fib(n) {
    if (n <= 1) return n;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let c = a + b;
        a = b;
        b = c;
    }
    return b;
}

let n = 10; // Example
console.log(fib(n));

#include <stdio.h>

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 10; // Example
    printf("%d\n", fib(n));
    return 0;
}

using System;

class Program {
    static int Fib(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1, c;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }

    static void Main() {
        int n = 10; // Example
        Console.WriteLine(Fib(n));
    }
}

The Python iterative approach achieves efficiency by only keeping track of the last two necessary Fibonacci numbers.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 4: Enumerate Boundaries + Ordered Set

We can enumerate the upper and lower boundaries i and j of the rectangle, then calculate the sum of the elements in each column within this boundary, and record it in the array nums. The problem is transformed into how to find the maximum subarray sum not exceeding k in the array nums.

We can use an ordered set to quickly find the maximum value less than or equal to x, thereby obtaining a subarray with the maximum subarray sum not exceeding k.

The time complexity is O(m^2 times n times log n), and the space complexity is O(n).

TypeScript

function maxSumSubmatrix(matrix: number[][], k: number): number {
    const m = matrix.length;
    const n = matrix[0].length;
    let ans = -Infinity;
    for (let i = 0; i < m; ++i) {
        const nums: number[] = new Array(n).fill(0);
        for (let j = i; j < m; ++j) {
            for (let h = 0; h < n; ++h) {
                nums[h] += matrix[j][h];
            }
            let s = 0;
            const ts: TreeSet<number> = new TreeSet<number>();
            ts.add(0);
            for (const x of nums) {
                s += x;
                const p = ts.ceil(s - k);
                if (p !== undefined) {
                    ans = Math.max(ans, s - p);
                }
                ts.add(s);
            }
        }
    }
    return ans;
}

type Compare<T> = (lhs: T, rhs: T) => number;

class RBTreeNode<T = number> {
    data: T;
    count: number;
    left: RBTreeNode<T> | null;
    right: RBTreeNode<T> | null;
    parent: RBTreeNode<T> | null;
    color: number;
    constructor(data: T) {
        this.data = data;
        this.left = this.right = this.parent = null;
        this.color = 0;
        this.count = 1;
    }

    sibling(): RBTreeNode<T> | null {
        if (!this.parent) return null; // sibling null if no parent
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }

    isOnLeft(): boolean {
        return this === this.parent!.left;
    }

    hasRedChild(): boolean {
        return (
            Boolean(this.left && this.left.color === 0) ||
            Boolean(this.right && this.right.color === 0)
        );
    }
}

class RBTree<T> {
    root: RBTreeNode<T> | null;
    lt: (l: T, r: T) => boolean;
    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
        this.root = null;
        this.lt = (l: T, r: T) => compare(l, r) < 0;
    }

    rotateLeft(pt: RBTreeNode<T>): void {
        const right = pt.right!;
        pt.right = right.left;

        if (pt.right) pt.right.parent = pt;
        right.parent = pt.parent;

        if (!pt.parent) this.root = right;
        else if (pt === pt.parent.left) pt.parent.left = right;
        else pt.parent.right = right;

        right.left = pt;
        pt.parent = right;
    }

    rotateRight(pt: RBTreeNode<T>): void {
        const left = pt.left!;
        pt.left = left.right;

        if (pt.left) pt.left.parent = pt;
        left.parent = pt.parent;

        if (!pt.parent) this.root = left;
        else if (pt === pt.parent.left) pt.parent.left = left;
        else pt.parent.right = left;

        left.right = pt;
        pt.parent = left;
    }

    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.color;
        p1.color = p2.color;
        p2.color = tmp;
    }

    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.data;
        p1.data = p2.data;
        p2.data = tmp;
    }

    fixAfterInsert(pt: RBTreeNode<T>): void {
        let parent = null;
        let grandParent = null;

        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
            parent = pt.parent;
            grandParent = pt.parent.parent;

            /*  Case : A
                Parent of pt is left child of Grand-parent of pt */
            if (parent === grandParent?.left) {
                const uncle = grandParent.right;

                /* Case : 1
                   The uncle of pt is also red
                   Only Recoloring required */
                if (uncle && uncle.color === 0) {
                    grandParent.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent;
                } else {
                    /* Case : 2
                       pt is right child of its parent
                       Left-rotation required */
                    if (pt === parent.right) {
                        this.rotateLeft(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is left child of its parent
                       Right-rotation required */
                    this.rotateRight(grandParent);
                    this.swapColor(parent!, grandParent);
                    pt = parent!;
                }
            } else {
                /* Case : B
               Parent of pt is right child of Grand-parent of pt */
                const uncle = grandParent!.left;

                /*  Case : 1
                    The uncle of pt is also red
                    Only Recoloring required */
                if (uncle != null && uncle.color === 0) {
                    grandParent!.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent!;
                } else {
                    /* Case : 2
                       pt is left child of its parent
                       Right-rotation required */
                    if (pt === parent.left) {
                        this.rotateRight(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is right child of its parent
                       Left-rotation required */
                    this.rotateLeft(grandParent!);
                    this.swapColor(parent!, grandParent!);
                    pt = parent!;
                }
            }
        }
        this.root!.color = 1;
    }

    delete(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        node.count--;
        if (!node.count) this.deleteNode(node);
        return true;
    }

    deleteAll(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        this.deleteNode(node);
        return true;
    }

    deleteNode(v: RBTreeNode<T>): void {
        const u = BSTreplace(v);

        // True when u and v are both black
        const uvBlack = (u === null || u.color === 1) && v.color === 1;
        const parent = v.parent!;

        if (!u) {
            // u is null therefore v is leaf
            if (v === this.root) this.root = null;
            // v is root, making root null
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    this.fixDoubleBlack(v);
                } else {
                    // u or v is red
                    if (v.sibling()) {
                        // sibling is not null, make it red"
                        v.sibling()!.color = 0;
                    }
                }
                // delete v from the tree
                if (v.isOnLeft()) parent.left = null;
                else parent.right = null;
            }
            return;
        }

        if (!v.left || !v.right) {
            // v has 1 child
            if (v === this.root) {
                // v is root, assign the value of u to v, and delete u
                v.data = u.data;
                v.left = v.right = null;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft()) parent.left = u;
                else parent.right = u;
                u.parent = parent;
                if (uvBlack) this.fixDoubleBlack(u);
                // u and v both black, fix double black at u
                else u.color = 1; // u or v red, color u black
            }
            return;
        }

        // v has 2 children, swap data with successor and recurse
        this.swapData(u, v);
        this.deleteNode(u);

        // find node that replaces a deleted node in BST
        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
            // when node have 2 children
            if (x.left && x.right) return successor(x.right);
            // when leaf
            if (!x.left && !x.right) return null;
            // when single child
            return x.left ?? x.right;
        }
        // find node that do not have a left child
        // in the subtree of the given node
        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
            let temp = x;
            while (temp.left) temp = temp.left;
            return temp;
        }
    }

    fixDoubleBlack(x: RBTreeNode<T>): void {
        if (x === this.root) return; // Reached root

        const sibling = x.sibling();
        const parent = x.parent!;
        if (!sibling) {
            // No sibiling, double black pushed up
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === 0) {
                // Sibling red
                parent.color = 0;
                sibling.color = 1;
                if (sibling.isOnLeft()) this.rotateRight(parent);
                // left case
                else this.rotateLeft(parent); // right case
                this.fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left && sibling.left.color === 0) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateRight(parent);
                        } else {
                            // right left
                            sibling.left.color = parent.color;
                            this.rotateRight(sibling);
                            this.rotateLeft(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right!.color = parent.color;
                            this.rotateLeft(sibling);
                            this.rotateRight(parent);
                        } else {
                            // right right
                            sibling.right!.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateLeft(parent);
                        }
                    }
                    parent.color = 1;
                } else {
                    // 2 black children
                    sibling.color = 0;
                    if (parent.color === 1) this.fixDoubleBlack(parent);
                    else parent.color = 1;
                }
            }
        }
    }

    insert(data: T): boolean {
        // search for a position to insert
        let parent = this.root;
        while (parent) {
            if (this.lt(data, parent.data)) {
                if (!parent.left) break;
                else parent = parent.left;
            } else if (this.lt(parent.data, data)) {
                if (!parent.right) break;
                else parent = parent.right;
            } else break;
        }

        // insert node into parent
        const node = new RBTreeNode(data);
        if (!parent) this.root = node;
        else if (this.lt(node.data, parent.data)) parent.left = node;
        else if (this.lt(parent.data, node.data)) parent.right = node;
        else {
            parent.count++;
            return false;
        }
        node.parent = parent;
        this.fixAfterInsert(node);
        return true;
    }

    find(data: T): RBTreeNode<T> | null {
        let p = this.root;
        while (p) {
            if (this.lt(data, p.data)) {
                p = p.left;
            } else if (this.lt(p.data, data)) {
                p = p.right;
            } else break;
        }
        return p ?? null;
    }

    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.inOrder(root.left!)) yield v;
        yield root.data;
        for (const v of this.inOrder(root.right!)) yield v;
    }

    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.reverseInOrder(root.right!)) yield v;
        yield root.data;
        for (const v of this.reverseInOrder(root.left!)) yield v;
    }
}

class TreeSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size += successful ? 1 : 0;
        return successful;
    }

    delete(val: T): boolean {
        const deleted = this.tree.deleteAll(val);
        this._size -= deleted ? 1 : 0;
        return deleted;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) yield val;
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) yield val;
        return undefined;
    }
}

class TreeMultiSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size++;
        return successful;
    }

    delete(val: T): boolean {
        const successful = this.tree.delete(val);
        if (!successful) return false;
        this._size--;
        return true;
    }

    count(val: T): number {
        const node = this.tree.find(val);
        return node ? node.count : 0;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        yield* this.values();
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the multi-set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }
}

func maxSumSubmatrix(matrix [][]int, k int) int {
	m, n := len(matrix), len(matrix[0])
	const inf = 1 << 30
	ans := -inf
	for i := 0; i < m; i++ {
		nums := make([]int, n)
		for j := i; j < m; j++ {
			for h := 0; h < n; h++ {
				nums[h] += matrix[j][h]
			}
			s := 0
			rbt := redblacktree.NewWithIntComparator()
			rbt.Put(0, nil)
			for _, x := range nums {
				s += x
				if y, ok := rbt.Ceiling(s - k); ok {
					ans = max(ans, s-y.Key.(int))
				}
				rbt.Put(s, nil)
			}
		}

	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Prefix Sum with Iteration	Time Complexity: O(n^2 * m log m), where m = num of rows and n = num of columns. Space Complexity: O(m) for storing row sums.
Recursive Approach with Memoization	Time Complexity: O(n) Space Complexity: O(n)
Iterative Approach	Time Complexity: O(n) Space Complexity: O(1)
Enumerate Boundaries + Ordered Set	–

Complexity analysis

Approach	Time	Space	When to Use
Prefix Sum with Iteration	O(m^2 * n^2)	O(1)	Simple implementation and good for understanding rectangle prefix sums
Prefix Sum + Ordered Set (Binary Search)	O(cols^2 * rows log rows)	O(rows)	Best general solution for large matrices and typical interview expectations
Recursive with Memoization	O(m * n * states)	O(m * n)	Useful for conceptual exploration or smaller input sizes

Frequently asked questions

Is Max Sum of Rectangle No Larger Than K easy or hard?

Max Sum of Rectangle No Larger Than K is classified as a Hard problem. It combines multiple concepts including 2D prefix sums, subarray optimization, and ordered sets, and requires reducing a matrix problem to repeated 1D searches.

Max Sum of Rectangle No Larger Than K Python or Java solution?

Python implementations typically use the bisect module with a sorted list to simulate an ordered set, while Java solutions commonly use TreeSet. Both maintain sorted prefix sums so binary search can find valid subarray sums in O(log n) time.

How to solve Max Sum of Rectangle No Larger Than K efficiently?

Convert the 2D rectangle problem into multiple 1D subarray problems. For every pair of columns, compute cumulative row sums and maintain prefix sums in a sorted structure. Use binary search to find the smallest prefix ≥ currentSum - k, which gives the best valid subarray ending at the current position.

What is the best approach for Max Sum of Rectangle No Larger Than K?

The most efficient approach uses prefix sums combined with an ordered set (such as a balanced BST). Fix two column boundaries, compress the rows into a 1D array, and then find the maximum subarray sum ≤ k using prefix sums and binary search. This reduces the problem to O(cols^2 * rows log rows) time and O(rows) space.

What data structure is used in Max Sum of Rectangle No Larger Than K?

The optimal solution uses an ordered set or balanced binary search tree to maintain prefix sums in sorted order. This structure enables efficient binary search to find the smallest prefix greater than or equal to currentSum - k while scanning the compressed array.

What is the time complexity of Max Sum of Rectangle No Larger Than K?

The optimal solution runs in O(cols^2 * rows log rows). Two columns are fixed to define the rectangle width, rows are compressed into a 1D array, and an ordered set is used to search prefix sums in O(log rows). Brute-force prefix-sum approaches can take O(m^2 * n^2).

Is Max Sum of Rectangle No Larger Than K asked at Google, Amazon, or Meta?

Max Sum of Rectangle No Larger Than K is a well-known hard matrix problem frequently associated with Google-style interviews. It tests prefix sums, binary search, and advanced data structures like ordered sets, which are common in high-level algorithm interviews.

Max Sum of Rectangle No Larger Than K solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum with Iteration

Approach 2: Recursive Approach with Memoization

Approach 3: Iterative Approach

Approach 4: Enumerate Boundaries + Ordered Set

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Max Sum of Rectangle No Larger Than K solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum with Iteration

Approach 2: Recursive Approach with Memoization

Approach 3: Iterative Approach

Approach 4: Enumerate Boundaries + Ordered Set

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems