Facebook Pixel

363. Max Sum of Rectangle No Larger Than K

HardArrayBinary SearchMatrixOrdered SetPrefix Sum
Leetcode Link

Problem Description

You are given an m x n matrix filled with integers and a target value k. Your task is to find a rectangle (submatrix) within this matrix that has the maximum possible sum, with the constraint that this sum must not exceed k.

The problem guarantees that at least one valid rectangle exists with a sum less than or equal to k.

For example, if you have a matrix and k = 2, you need to find all possible rectangles within the matrix, calculate their sums, filter out those with sums greater than k, and return the maximum sum among the remaining valid rectangles.

The solution approach transforms this 2D problem into a 1D problem by:

  1. Fixing the top and bottom boundaries of potential rectangles (rows i to j)
  2. Compressing the rows between these boundaries into a single array nums where each element represents the column sum within the fixed row boundaries
  3. Finding the maximum subarray sum in nums that doesn't exceed k using a sorted set to efficiently track prefix sums

The sorted set maintains prefix sums seen so far. For each new prefix sum s, we search for the smallest prefix sum p such that s - p ≤ k (equivalently, p ≥ s - k). The difference s - p gives us a subarray sum that doesn't exceed k, and we track the maximum such sum across all possible rectangles.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is recognizing that finding the maximum sum rectangle in a 2D matrix can be reduced to solving multiple 1D maximum subarray problems.

Think about how rectangles are formed in a matrix - every rectangle has four boundaries: top, bottom, left, and right. If we fix the top and bottom boundaries, we essentially "compress" multiple rows into a single row where each element represents the sum of elements in that column between our fixed boundaries.

For instance, if we fix rows i to j, we can create an array where nums[col] = sum of all elements in column col from row i to row j. Now the problem becomes: find the maximum subarray sum in this 1D array nums that doesn't exceed k.

The 1D subarray problem with a constraint is where the clever use of prefix sums and a sorted set comes in. When we have a prefix sum s at the current position, we want to find a previous prefix sum p such that s - p (the subarray sum) is as large as possible but still ≤ k. This means we need p ≥ s - k, and we want the smallest such p to maximize s - p.

A sorted set allows us to efficiently find this smallest p that is greater than or equal to s - k using binary search (bisect_left). We maintain all previous prefix sums in the sorted set, including 0 (for subarrays starting from the beginning).

By trying all possible pairs of top and bottom boundaries and solving the 1D problem for each, we ensure we've considered all possible rectangles in the matrix and found the one with maximum sum not exceeding k.

Solution Approach

The implementation follows a three-layer nested approach to explore all possible rectangles:

Step 1: Enumerate Top Boundaries We iterate through each possible top row i from 0 to m-1. This will serve as the upper boundary of our rectangles.

Step 2: Enumerate Bottom Boundaries For each fixed top row i, we enumerate all possible bottom rows j from i to m-1. This gives us all possible row ranges [i, j].

Step 3: Compress Rows into Column Sums For each row range [i, j], we maintain an array nums where nums[h] represents the sum of elements in column h from row i to row j. This is done incrementally:

  • When j = i, we initialize nums[h] = matrix[i][h]
  • As we extend to j+1, we update nums[h] += matrix[j+1][h]

Step 4: Find Maximum Subarray Sum ≤ k With the compressed 1D array nums, we need to find the maximum subarray sum that doesn't exceed k. This is accomplished using:

  1. Prefix Sum Calculation: We maintain a running sum s as we traverse the array.

  2. Sorted Set for Efficient Search: We use a SortedSet (ordered set) to store all previous prefix sums, initialized with 0 to handle subarrays starting from index 0.

  3. Binary Search for Valid Subarrays: For each position with prefix sum s:

    • We search for the smallest prefix sum p where p >= s - k using bisect_left(s - k)
    • If such a p exists, the subarray sum s - p is valid (≤ k)
    • We update our answer with max(ans, s - p)
    • Add current prefix sum s to the sorted set for future iterations

Time Complexity: O(m² × n × log n) where:

  • O(m²) for enumerating all row ranges
  • O(n) for processing each column
  • O(log n) for binary search operations in the sorted set

Space Complexity: O(n) for the nums array and the sorted set which can contain at most n prefix sums.

The algorithm guarantees finding the maximum sum rectangle not exceeding k by exhaustively checking all possible rectangles through the row boundary enumeration and efficiently solving the constrained 1D subarray problem.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider the matrix:

matrix = [[2, 1],
          [1, 2]]
k = 3

Step 1: Fix top boundary at row 0 (i = 0)

  • Bottom boundary at row 0 (j = 0):

    • Compress rows [0,0] into column sums: nums = [2, 1]
    • Find max subarray sum ≤ 3 in nums:
      • Start with sorted set = {0}
      • Position 0: prefix sum s = 2
        • Search for p ≥ 2-3 = -1, found p = 0
        • Subarray sum = 2-0 = 2 ≤ 3 ✓
        • Update answer = 2
        • Add 2 to set: {0, 2}
      • Position 1: prefix sum s = 2+1 = 3
        • Search for p ≥ 3-3 = 0, found p = 0
        • Subarray sum = 3-0 = 3 ≤ 3 ✓
        • Update answer = 3
        • Add 3 to set: {0, 2, 3}

  • Bottom boundary at row 1 (j = 1):

    • Compress rows [0,1] into column sums: nums = [2+1, 1+2] = [3, 3]
    • Find max subarray sum ≤ 3 in nums:
      • Start with sorted set = {0}
      • Position 0: prefix sum s = 3
        • Search for p ≥ 3-3 = 0, found p = 0
        • Subarray sum = 3-0 = 3 ≤ 3 ✓
        • Answer remains 3
        • Add 3 to set: {0, 3}
      • Position 1: prefix sum s = 3+3 = 6
        • Search for p ≥ 6-3 = 3, found p = 3
        • Subarray sum = 6-3 = 3 ≤ 3 ✓
        • Answer remains 3

Step 2: Fix top boundary at row 1 (i = 1)

  • Bottom boundary at row 1 (j = 1):
    • Compress rows [1,1] into column sums: nums = [1, 2]
    • Find max subarray sum ≤ 3 in nums:
      • Position 0: prefix sum s = 1, subarray sum = 1 ≤ 3 ✓
      • Position 1: prefix sum s = 3, subarray sum = 3 ≤ 3 ✓
      • Answer remains 3

Final Result: 3

The maximum rectangle sum not exceeding k=3 is achieved by:

  • The single element at position [1,1] with value 2
  • The first row [2, 1] with sum 3
  • The first column [2, 1] with sum 3
  • The second column [1, 2] with sum 3

All have sum = 3, which is the maximum possible without exceeding k.

Solution Implementation

1from typing import List
2from sortedcontainers import SortedList
3import math
4
5class Solution:
6    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
7        """
8        Find the maximum sum of a rectangle in the matrix such that its sum is no larger than k.
9      
10        Args:
11            matrix: 2D list of integers
12            k: Target upper bound for rectangle sum
13          
14        Returns:
15            Maximum sum of rectangle that doesn't exceed k
16        """
17        rows, cols = len(matrix), len(matrix[0])
18        max_sum = -math.inf
19      
20        # Fix the top row of the rectangle
21        for top_row in range(rows):
22            # Initialize column sums for current top row
23            column_sums = [0] * cols
24          
25            # Extend the rectangle by moving the bottom row down
26            for bottom_row in range(top_row, rows):
27                # Add current row values to column sums
28                for col in range(cols):
29                    column_sums[col] += matrix[bottom_row][col]
30              
31                # Now we have a 1D array problem: find max subarray sum <= k
32                # Use prefix sum with sorted set to efficiently find the answer
33                current_sum = 0
34                # Store prefix sums in sorted order, initialize with 0
35                prefix_sums = SortedList([0])
36              
37                for value in column_sums:
38                    current_sum += value
39                    # We need to find smallest prefix_sum such that:
40                    # current_sum - prefix_sum <= k
41                    # Which means: prefix_sum >= current_sum - k
42                    target = current_sum - k
43                    index = prefix_sums.bisect_left(target)
44                  
45                    # If we found a valid prefix sum
46                    if index < len(prefix_sums):
47                        # Update max_sum with the rectangle sum
48                        max_sum = max(max_sum, current_sum - prefix_sums[index])
49                  
50                    # Add current prefix sum for future iterations
51                    prefix_sums.add(current_sum)
52      
53        return max_sum
54
1class Solution {
2    public int maxSumSubmatrix(int[][] matrix, int k) {
3        int rows = matrix.length;
4        int cols = matrix[0].length;
5        final int NEGATIVE_INFINITY = Integer.MIN_VALUE;
6        int maxSum = NEGATIVE_INFINITY;
7      
8        // Fix the top row of the submatrix
9        for (int topRow = 0; topRow < rows; topRow++) {
10            // Array to store column sums between topRow and bottomRow
11            int[] columnSums = new int[cols];
12          
13            // Iterate through all possible bottom rows
14            for (int bottomRow = topRow; bottomRow < rows; bottomRow++) {
15                // Update column sums to include current bottom row
16                for (int col = 0; col < cols; col++) {
17                    columnSums[col] += matrix[bottomRow][col];
18                }
19              
20                // Find maximum subarray sum <= k using prefix sums and TreeSet
21                int currentPrefixSum = 0;
22                TreeSet<Integer> prefixSumSet = new TreeSet<>();
23                // Add 0 to handle subarrays starting from index 0
24                prefixSumSet.add(0);
25              
26                // Process each column sum
27                for (int colSum : columnSums) {
28                    currentPrefixSum += colSum;
29                  
30                    // Find the smallest prefix sum >= (currentPrefixSum - k)
31                    // This gives us the maximum subarray sum <= k
32                    Integer minPrefixSum = prefixSumSet.ceiling(currentPrefixSum - k);
33                  
34                    if (minPrefixSum != null) {
35                        // Update maxSum with the subarray sum (currentPrefixSum - minPrefixSum)
36                        maxSum = Math.max(maxSum, currentPrefixSum - minPrefixSum);
37                    }
38                  
39                    // Add current prefix sum to the set for future iterations
40                    prefixSumSet.add(currentPrefixSum);
41                }
42            }
43        }
44      
45        return maxSum;
46    }
47}
48
1class Solution {
2public:
3    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
4        int rows = matrix.size();
5        int cols = matrix[0].size();
6        const int NEGATIVE_INF = INT_MIN;  // Use standard INT_MIN for negative infinity
7        int maxSum = NEGATIVE_INF;
8      
9        // Fix top boundary of the rectangle at row i
10        for (int topRow = 0; topRow < rows; ++topRow) {
11            // Array to store column sums between topRow and bottomRow
12            vector<int> columnSums(cols, 0);
13          
14            // Extend bottom boundary of the rectangle from topRow to last row
15            for (int bottomRow = topRow; bottomRow < rows; ++bottomRow) {
16                // Add current row values to column sums
17                for (int col = 0; col < cols; ++col) {
18                    columnSums[col] += matrix[bottomRow][col];
19                }
20              
21                // Now we have a 1D array problem: find max subarray sum <= k
22                // Use ordered set to efficiently find the required prefix sum
23                set<int> prefixSums;
24                prefixSums.insert(0);  // Empty prefix for subarrays starting at index 0
25                int currentPrefixSum = 0;
26              
27                // Iterate through the compressed 1D array
28                for (int colSum : columnSums) {
29                    currentPrefixSum += colSum;
30                  
31                    // We want to find largest subarray sum <= k
32                    // If current prefix is currentPrefixSum and we want sum <= k,
33                    // we need to find smallest previous prefix >= currentPrefixSum - k
34                    auto iterator = prefixSums.lower_bound(currentPrefixSum - k);
35                  
36                    if (iterator != prefixSums.end()) {
37                        // Found a valid prefix, calculate the subarray sum
38                        int subarraySum = currentPrefixSum - *iterator;
39                        maxSum = max(maxSum, subarraySum);
40                    }
41                  
42                    // Add current prefix sum for future iterations
43                    prefixSums.insert(currentPrefixSum);
44                }
45            }
46        }
47      
48        return maxSum;
49    }
50};
51
1/**
2 * Find the maximum sum of a rectangle in a matrix such that the sum is no larger than k
3 * Time Complexity: O(m^2 * n * log n) where m is rows and n is columns
4 * Space Complexity: O(n)
5 * 
6 * @param matrix - The input 2D matrix
7 * @param k - The upper bound for the rectangle sum
8 * @returns The maximum sum that is no larger than k
9 */
10function maxSumSubmatrix(matrix: number[][], k: number): number {
11    const numRows = matrix.length;
12    const numCols = matrix[0].length;
13    let maxSum = -Infinity;
14  
15    // Fix the top row of the rectangle
16    for (let topRow = 0; topRow < numRows; ++topRow) {
17        // Array to store column sums between topRow and bottomRow
18        const columnSums: number[] = new Array(numCols).fill(0);
19      
20        // Expand the bottom row of the rectangle
21        for (let bottomRow = topRow; bottomRow < numRows; ++bottomRow) {
22            // Update column sums for the current rectangle
23            for (let col = 0; col < numCols; ++col) {
24                columnSums[col] += matrix[bottomRow][col];
25            }
26          
27            // Now we have a 1D array problem: find max subarray sum <= k
28            let currentSum = 0;
29            const prefixSums: TreeSet<number> = new TreeSet<number>();
30            prefixSums.add(0); // Add 0 to handle subarrays starting from index 0
31          
32            // Iterate through the column sums
33            for (const columnValue of columnSums) {
34                currentSum += columnValue;
35              
36                // Find the smallest prefix sum >= (currentSum - k)
37                // This gives us the maximum subarray sum <= k
38                const minPrefixSum = prefixSums.ceil(currentSum - k);
39              
40                if (minPrefixSum !== undefined) {
41                    // Update max sum if we found a better one
42                    maxSum = Math.max(maxSum, currentSum - minPrefixSum);
43                }
44              
45                // Add current prefix sum for future iterations
46                prefixSums.add(currentSum);
47            }
48        }
49    }
50  
51    return maxSum;
52}
53
54// The TreeSet and supporting classes remain the same as they are utility data structures
55// They implement a self-balancing binary search tree (Red-Black Tree) for O(log n) operations
56
57type Compare<T> = (lhs: T, rhs: T) => number;
58
59class RBTreeNode<T = number> {
60    data: T;
61    count: number;
62    left: RBTreeNode<T> | null;
63    right: RBTreeNode<T> | null;
64    parent: RBTreeNode<T> | null;
65    color: number; // 0 = red, 1 = black
66  
67    constructor(data: T) {
68        this.data = data;
69        this.left = this.right = this.parent = null;
70        this.color = 0; // New nodes are red
71        this.count = 1;
72    }
73
74    sibling(): RBTreeNode<T> | null {
75        if (!this.parent) return null;
76        return this.isOnLeft() ? this.parent.right : this.parent.left;
77    }
78
79    isOnLeft(): boolean {
80        return this === this.parent!.left;
81    }
82
83    hasRedChild(): boolean {
84        return (
85            Boolean(this.left && this.left.color === 0) ||
86            Boolean(this.right && this.right.color === 0)
87        );
88    }
89}
90
91class RBTree<T> {
92    root: RBTreeNode<T> | null;
93    lt: (l: T, r: T) => boolean;
94  
95    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
96        this.root = null;
97        this.lt = (l: T, r: T) => compare(l, r) < 0;
98    }
99
100    rotateLeft(pt: RBTreeNode<T>): void {
101        const right = pt.right!;
102        pt.right = right.left;
103
104        if (pt.right) pt.right.parent = pt;
105        right.parent = pt.parent;
106
107        if (!pt.parent) this.root = right;
108        else if (pt === pt.parent.left) pt.parent.left = right;
109        else pt.parent.right = right;
110
111        right.left = pt;
112        pt.parent = right;
113    }
114
115    rotateRight(pt: RBTreeNode<T>): void {
116        const left = pt.left!;
117        pt.left = left.right;
118
119        if (pt.left) pt.left.parent = pt;
120        left.parent = pt.parent;
121
122        if (!pt.parent) this.root = left;
123        else if (pt === pt.parent.left) pt.parent.left = left;
124        else pt.parent.right = left;
125
126        left.right = pt;
127        pt.parent = left;
128    }
129
130    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
131        const tmp = p1.color;
132        p1.color = p2.color;
133        p2.color = tmp;
134    }
135
136    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
137        const tmp = p1.data;
138        p1.data = p2.data;
139        p2.data = tmp;
140    }
141
142    fixAfterInsert(pt: RBTreeNode<T>): void {
143        let parent = null;
144        let grandParent = null;
145
146        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
147            parent = pt.parent;
148            grandParent = pt.parent.parent;
149
150            if (parent === grandParent?.left) {
151                const uncle = grandParent.right;
152
153                if (uncle && uncle.color === 0) {
154                    grandParent.color = 0;
155                    parent.color = 1;
156                    uncle.color = 1;
157                    pt = grandParent;
158                } else {
159                    if (pt === parent.right) {
160                        this.rotateLeft(parent);
161                        pt = parent;
162                        parent = pt.parent;
163                    }
164
165                    this.rotateRight(grandParent);
166                    this.swapColor(parent!, grandParent);
167                    pt = parent!;
168                }
169            } else {
170                const uncle = grandParent!.left;
171
172                if (uncle != null && uncle.color === 0) {
173                    grandParent!.color = 0;
174                    parent.color = 1;
175                    uncle.color = 1;
176                    pt = grandParent!;
177                } else {
178                    if (pt === parent.left) {
179                        this.rotateRight(parent);
180                        pt = parent;
181                        parent = pt.parent;
182                    }
183
184                    this.rotateLeft(grandParent!);
185                    this.swapColor(parent!, grandParent!);
186                    pt = parent!;
187                }
188            }
189        }
190        this.root!.color = 1;
191    }
192
193    delete(val: T): boolean {
194        const node = this.find(val);
195        if (!node) return false;
196        node.count--;
197        if (!node.count) this.deleteNode(node);
198        return true;
199    }
200
201    deleteAll(val: T): boolean {
202        const node = this.find(val);
203        if (!node) return false;
204        this.deleteNode(node);
205        return true;
206    }
207
208    deleteNode(v: RBTreeNode<T>): void {
209        const u = BSTreplace(v);
210        const uvBlack = (u === null || u.color === 1) && v.color === 1;
211        const parent = v.parent!;
212
213        if (!u) {
214            if (v === this.root) this.root = null;
215            else {
216                if (uvBlack) {
217                    this.fixDoubleBlack(v);
218                } else {
219                    if (v.sibling()) {
220                        v.sibling()!.color = 0;
221                    }
222                }
223                if (v.isOnLeft()) parent.left = null;
224                else parent.right = null;
225            }
226            return;
227        }
228
229        if (!v.left || !v.right) {
230            if (v === this.root) {
231                v.data = u.data;
232                v.left = v.right = null;
233            } else {
234                if (v.isOnLeft()) parent.left = u;
235                else parent.right = u;
236                u.parent = parent;
237                if (uvBlack) this.fixDoubleBlack(u);
238                else u.color = 1;
239            }
240            return;
241        }
242
243        this.swapData(u, v);
244        this.deleteNode(u);
245
246        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
247            if (x.left && x.right) return successor(x.right);
248            if (!x.left && !x.right) return null;
249            return x.left ?? x.right;
250        }
251
252        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
253            let temp = x;
254            while (temp.left) temp = temp.left;
255            return temp;
256        }
257    }
258
259    fixDoubleBlack(x: RBTreeNode<T>): void {
260        if (x === this.root) return;
261
262        const sibling = x.sibling();
263        const parent = x.parent!;
264        if (!sibling) {
265            this.fixDoubleBlack(parent);
266        } else {
267            if (sibling.color === 0) {
268                parent.color = 0;
269                sibling.color = 1;
270                if (sibling.isOnLeft()) this.rotateRight(parent);
271                else this.rotateLeft(parent);
272                this.fixDoubleBlack(x);
273            } else {
274                if (sibling.hasRedChild()) {
275                    if (sibling.left && sibling.left.color === 0) {
276                        if (sibling.isOnLeft()) {
277                            sibling.left.color = sibling.color;
278                            sibling.color = parent.color;
279                            this.rotateRight(parent);
280                        } else {
281                            sibling.left.color = parent.color;
282                            this.rotateRight(sibling);
283                            this.rotateLeft(parent);
284                        }
285                    } else {
286                        if (sibling.isOnLeft()) {
287                            sibling.right!.color = parent.color;
288                            this.rotateLeft(sibling);
289                            this.rotateRight(parent);
290                        } else {
291                            sibling.right!.color = sibling.color;
292                            sibling.color = parent.color;
293                            this.rotateLeft(parent);
294                        }
295                    }
296                    parent.color = 1;
297                } else {
298                    sibling.color = 0;
299                    if (parent.color === 1) this.fixDoubleBlack(parent);
300                    else parent.color = 1;
301                }
302            }
303        }
304    }
305
306    insert(data: T): boolean {
307        let parent = this.root;
308        while (parent) {
309            if (this.lt(data, parent.data)) {
310                if (!parent.left) break;
311                else parent = parent.left;
312            } else if (this.lt(parent.data, data)) {
313                if (!parent.right) break;
314                else parent = parent.right;
315            } else break;
316        }
317
318        const node = new RBTreeNode(data);
319        if (!parent) this.root = node;
320        else if (this.lt(node.data, parent.data)) parent.left = node;
321        else if (this.lt(parent.data, node.data)) parent.right = node;
322        else {
323            parent.count++;
324            return false;
325        }
326        node.parent = parent;
327        this.fixAfterInsert(node);
328        return true;
329    }
330
331    find(data: T): RBTreeNode<T> | null {
332        let p = this.root;
333        while (p) {
334            if (this.lt(data, p.data)) {
335                p = p.left;
336            } else if (this.lt(p.data, data)) {
337                p = p.right;
338            } else break;
339        }
340        return p ?? null;
341    }
342
343    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
344        if (!root) return;
345        for (const v of this.inOrder(root.left!)) yield v;
346        yield root.data;
347        for (const v of this.inOrder(root.right!)) yield v;
348    }
349
350    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
351        if (!root) return;
352        for (const v of this.reverseInOrder(root.right!)) yield v;
353        yield root.data;
354        for (const v of this.reverseInOrder(root.left!)) yield v;
355    }
356}
357
358class TreeSet<T = number> {
359    _size: number;
360    tree: RBTree<T>;
361    compare: Compare<T>;
362  
363    constructor(
364        collection: T[] | Compare<T> = [],
365        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
366    ) {
367        if (typeof collection === 'function') {
368            compare = collection;
369            collection = [];
370        }
371        this._size = 0;
372        this.compare = compare;
373        this.tree = new RBTree(compare);
374        for (const val of collection) this.add(val);
375    }
376
377    size(): number {
378        return this._size;
379    }
380
381    has(val: T): boolean {
382        return !!this.tree.find(val);
383    }
384
385    add(val: T): boolean {
386        const successful = this.tree.insert(val);
387        this._size += successful ? 1 : 0;
388        return successful;
389    }
390
391    delete(val: T): boolean {
392        const deleted = this.tree.deleteAll(val);
393        this._size -= deleted ? 1 : 0;
394        return deleted;
395    }
396
397    ceil(val: T): T | undefined {
398        let p = this.tree.root;
399        let higher = null;
400        while (p) {
401            if (this.compare(p.data, val) >= 0) {
402                higher = p;
403                p = p.left;
404            } else {
405                p = p.right;
406            }
407        }
408        return higher?.data;
409    }
410
411    floor(val: T): T | undefined {
412        let p = this.tree.root;
413        let lower = null;
414        while (p) {
415            if (this.compare(val, p.data) >= 0) {
416                lower = p;
417                p = p.right;
418            } else {
419                p = p.left;
420            }
421        }
422        return lower?.data;
423    }
424
425    higher(val: T): T | undefined {
426        let p = this.tree.root;
427        let higher = null;
428        while (p) {
429            if (this.compare(val, p.data) < 0) {
430                higher = p;
431                p = p.left;
432            } else {
433                p = p.right;
434            }
435        }
436        return higher?.data;
437    }
438
439    lower(val: T): T | undefined {
440        let p = this.tree.root;
441        let lower = null;
442        while (p) {
443            if (this.compare(p.data, val) < 0) {
444                lower = p;
445                p = p.right;
446            } else {
447                p = p.left;
448            }
449        }
450        return lower?.data;
451    }
452
453    first(): T | undefined {
454        return this.tree.inOrder().next().value;
455    }
456
457    last(): T | undefined {
458        return this.tree.reverseInOrder().next().value;
459    }
460
461    shift(): T | undefined {
462        const first = this.first();
463        if (first === undefined) return undefined;
464        this.delete(first);
465        return first;
466    }
467
468    pop(): T | undefined {
469        const last = this.last();
470        if (last === undefined) return undefined;
471        this.delete(last);
472        return last;
473    }
474
475    *[Symbol.iterator](): Generator<T, void, void> {
476        for (const val of this.values()) yield val;
477    }
478
479    *keys(): Generator<T, void, void> {
480        for (const val of this.values()) yield val;
481    }
482
483    *values(): Generator<T, undefined, void> {
484        for (const val of this.tree.inOrder()) yield val;
485        return undefined;
486    }
487
488    *rvalues(): Generator<T, undefined, void> {
489        for (const val of this.tree.reverseInOrder()) yield val;
490        return undefined;
491    }
492}
493

Time and Space Complexity

Time Complexity: O(m^2 × n × log n)

The analysis breaks down as follows:

  • The outer loop iterates through all possible top rows: O(m) iterations
  • The middle loop iterates through all possible bottom rows starting from the current top row: O(m) iterations in total
  • For each rectangle defined by top and bottom rows:
    • We compute the column sums by iterating through all columns: O(n)
    • We then iterate through the column sums array: O(n) iterations
    • For each element in the column sums, we perform:
      • bisect_left operation on the SortedSet: O(log n) as the set can contain at most n+1 elements
      • add operation to the SortedSet: O(log n)

Combining these operations: O(m) × O(m) × [O(n) + O(n) × O(log n)] = O(m^2 × n × log n)

Space Complexity: O(n)

The space usage consists of:

  • nums array to store column sums: O(n)
  • SortedSet ts which stores at most n+1 prefix sums (one initial 0 and one for each column): O(n)
  • Other variables like ans, s, p: O(1)

The dominant space usage is O(n), giving us an overall space complexity of O(n).

Common Pitfalls

1. Incorrect Initialization of Prefix Sum Set

Pitfall: Forgetting to initialize the sorted set with 0, which causes the algorithm to miss rectangles that start from the leftmost column.

Wrong Implementation:

prefix_sums = SortedList()  # Missing the initial 0

Why It's Wrong: Without the initial 0 in the prefix sum set, we cannot properly handle subarrays that start from index 0. For example, if the first few columns sum to a valid value ≤ k, we need 0 in our set to compute current_sum - 0.

Correct Implementation:

prefix_sums = SortedList([0])  # Initialize with 0

2. Using Wrong Binary Search Method

Pitfall: Using bisect_right instead of bisect_left when searching for the smallest valid prefix sum.

Wrong Implementation:

index = prefix_sums.bisect_right(target)  # Wrong method

Why It's Wrong: We need the smallest prefix sum p such that p >= current_sum - k. Using bisect_right would give us the insertion point after all equal values, potentially missing valid solutions when there are duplicate prefix sums.

Correct Implementation:

index = prefix_sums.bisect_left(target)  # Find leftmost valid position

3. Reinitializing Column Sums Incorrectly

Pitfall: Creating a new column_sums array for each bottom_row instead of accumulating values.

Wrong Implementation:

for bottom_row in range(top_row, rows):
    column_sums = [matrix[bottom_row][col] for col in range(cols)]  # Wrong: overwrites previous sums

Why It's Wrong: This resets the column sums for each new bottom row, losing the accumulation from previous rows in the range [top_row, bottom_row-1].

Correct Implementation:

column_sums = [0] * cols  # Initialize once per top_row
for bottom_row in range(top_row, rows):
    for col in range(cols):
        column_sums[col] += matrix[bottom_row][col]  # Accumulate

4. Adding Prefix Sum Before Checking

Pitfall: Adding the current prefix sum to the sorted set before using it to find valid subarrays.

Wrong Implementation:

for value in column_sums:
    current_sum += value
    prefix_sums.add(current_sum)  # Added too early
    target = current_sum - k
    index = prefix_sums.bisect_left(target)
    # ... rest of logic

Why It's Wrong: This would allow the algorithm to use the current prefix sum to form a subarray with itself, resulting in an empty subarray (sum = 0), which may not be the intended behavior.

Correct Implementation:

for value in column_sums:
    current_sum += value
    target = current_sum - k
    index = prefix_sums.bisect_left(target)
    if index < len(prefix_sums):
        max_sum = max(max_sum, current_sum - prefix_sums[index])
    prefix_sums.add(current_sum)  # Add after checking

5. Not Handling Edge Cases with Initial Maximum

Pitfall: Initializing max_sum with 0 or a small fixed value instead of negative infinity.

Wrong Implementation:

max_sum = 0  # Wrong if all valid rectangles have negative sums

Why It's Wrong: If all elements in the matrix are negative and k is negative, the maximum valid rectangle sum could be negative. Starting with 0 would incorrectly return 0.

Correct Implementation:

max_sum = -math.inf  # Or float('-inf')
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More