LeetCode 363: Max Sum of Rectangle No Larger Than K Solution in Python – A Step-by-Step Guide

Imagine you’re given a grid of numbers—like a treasure map—and you need to find a rectangle within it whose sum is as large as possible but doesn’t exceed a given limit, K. That’s the challenge of LeetCode 363: Max Sum of Rectangle No Larger Than K, a hard-level problem that blends grid traversal with optimization. Using Python, we’ll explore two solutions: the Best Solution—prefix sums with binary search for O(m²nlog n) efficiency—and an Alternative Solution—brute force at O(m²*n²). With examples, clear code breakdowns, and a friendly vibe, this guide will help you uncover that max sum. Let’s start exploring!

What Is LeetCode 363: Max Sum of Rectangle No Larger Than K?

LeetCode 363: Max Sum of Rectangle No Larger Than K provides a 2D matrix of integers and a target K. Your task is to find the maximum sum of any rectangle (submatrix) in the grid such that the sum is ≤ K. It’s an extension of the 1D max subarray problem into two dimensions—challenging but rewarding!

Problem Statement

Input:

matrix: 2D list of integers.
k: Integer representing the upper bound for the sum.

Output: Integer - Maximum sum of a rectangle ≤ K.
Rules:

Rectangle must be contiguous (rows and columns consecutive).
Return the largest sum that does not exceed K.

Constraints

1 <= m, n <= 200 (m rows, n columns)
-10⁵ <= matrix[i][j] <= 10⁵
-10⁹ <= k <= 10⁹

Examples

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

Output: 2

Rectangle [1,0], [0,-2] sums to -1 < 2.
Rectangle [1] sums to 1 < 2.
Rectangle [3] sums to 3 > 2.
Best: [2] (bottom-right corner) = 2 ≤ 2.

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

Output: 3

[2,2] = 4 > 3, [2] = 2 < 3, [2,-1] = 1 < 3, best: [2,2,-1] = 3 ≤ 3.

These show the balancing act—let’s solve it!

Understanding the Problem: Finding the Max Sum Rectangle

To tackle LeetCode 363 in Python, we need to: 1. Identify all possible rectangles in the matrix. 2. Compute their sums. 3. Find the maximum sum that’s ≤ K.

A naive approach might check every rectangle, but that’s too slow. Instead, we’ll use:

Best Solution: Prefix sums with binary search—O(m²*n*log n) time, O(n) space—efficient and clever.
Alternative Solution: Brute force—O(m²*n²) time, O(1) space—simple but impractical.

Let’s optimize with the best solution!

Best Solution: Prefix Sums with Binary Search

Why This Is the Best Solution

The prefix sums with binary search approach reduces complexity to O(m²nlog n) by:

Fixing column pairs (m² combinations).
Using prefix sums to compute row sums in O(n).
Using a sorted set and binary search to find the max sum ≤ K in O(log n).

It’s the fastest practical solution—leveraging 1D subarray techniques in 2D!

How It Works

Think of it like slicing the grid:

Fix Columns: For each pair of columns, compute cumulative sums across rows.
Prefix Sums: Treat the column pair as a 1D array of row sums.
Binary Search: For each prefix sum, find the largest prior sum such that their difference is ≤ K.
Maximize: Track the maximum valid sum.

It’s like flattening 2D into 1D and optimizing!

Step-by-Step Example

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

Grid:

1 0 1 0 -2 3

Col 0-0:

Sums: [1, 0] → Prefix: [0, 1, 1].
Differences: 1-0=1 ≤ 2, max_sum=1.

Col 0-1:

Sums: [1, -2] → Prefix: [0, 1, -1].
Differences: 1-0=1, -1-0=-1, -1-1=-2, max_sum=1.

Col 0-2:

Sums: [2, 1] → Prefix: [0, 2, 3].
Differences: 2-0=2 ≤ 2, 3-2=1 ≤ 2, 3-0=3 > 2, max_sum=2.

Col 1-1:

Sums: [-2] → Prefix: [0, -2].
Differences: -2-0=-2 ≤ 2, max_sum=2.

Col 1-2:

Sums: [-1, 1] → Prefix: [0, -1, 0].
Differences: -1-0=-1, 0-(-1)=1, 0-0=0, max_sum=2.

Col 2-2:

Sums: [1, 3] → Prefix: [0, 1, 4].
Differences: 1-0=1, 4-1=3 > 2, 4-0=4 > 2, max_sum=2.

Result: 2 (e.g., [3] at (1,2)).

Code with Explanation

Here’s the Python code using prefix sums and binary search:

from bisect import bisect_right
from sortedcontainers import SortedList

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        max_sum = float('-inf')

        # Iterate over all column pairs
        for left in range(n):
            # Cumulative row sums between left and right columns
            row_sums = [0] * m
            for right in range(left, n):
                # Update row_sums for current column pair
                for i in range(m):
                    row_sums[i] += matrix[i][right]

                # Use prefix sums and binary search on row_sums
                prefix_sums = SortedList([0])  # Include 0 for full array
                curr_sum = 0
                for row_sum in row_sums:
                    curr_sum += row_sum
                    # Find largest prefix_sum <= curr_sum - k
                    idx = bisect_right(prefix_sums, curr_sum - k)
                    if idx > 0:
                        prev_sum = prefix_sums[idx - 1]
                        max_sum = max(max_sum, curr_sum - prev_sum)
                    prefix_sums.add(curr_sum)

        return max_sum

Explanation

Lines 5-7: Handle empty matrix case.
Lines 9-10: Initialize dimensions and max_sum.
Lines 12-28: Main logic:

Line 13: Outer loop over left column.
Line 15: row_sums tracks cumulative sums for rows between left and right.
Lines 16-19: Inner loop updates row_sums by adding each column’s values.
Line 21: prefix_sums (SortedList) stores cumulative sums, starting with 0.
Lines 23-28: For each row sum:

Update curr_sum.
Use bisect_right to find the insertion point for curr_sum - k.
If a prior sum exists (idx > 0), compute subarray sum and update max_sum.
Add curr_sum to prefix_sums.

Line 30: Return the maximum sum found.

Time Complexity: O(m²*n*log n)—m² column pairs, n row sums, log n binary search.
Space Complexity: O(n)—prefix_sums stores up to n+1 values.

This is like slicing the grid and searching smartly—super efficient!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute force solution is O(m²*n²) but straightforward—check every possible rectangle and its sum. It’s slow but easy to understand—great for grasping the problem before optimizing!

How It Works

Enumerate: Try all top-left and bottom-right corners.
Compute: Sum each rectangle.
Maximize: Track max sum ≤ K.

Step-by-Step Example

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

Rectangles:

(0,0)-(0,0): [1] = 1.
(0,0)-(0,1): [1,0] = 1.
(0,0)-(0,2): [1,0,1] = 2.
(0,0)-(1,0): [1,0] = 1.
(1,2)-(1,2): [3] = 3 > 2.
And so on...

Max: 2 (e.g., [1,0,1]).

Code with Explanation

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        max_sum = float('-inf')

        # Try all possible rectangles
        for top in range(m):
            for left in range(n):
                for bottom in range(top, m):
                    for right in range(left, n):
                        # Compute sum of rectangle
                        curr_sum = 0
                        for i in range(top, bottom + 1):
                            for j in range(left, right + 1):
                                curr_sum += matrix[i][j]
                        if curr_sum <= k:
                            max_sum = max(max_sum, curr_sum)

        return max_sum if max_sum != float('-inf') else 0

Explanation

Lines 7-19: Four nested loops:

Outer two: Top-left corner (top, left).
Inner two: Bottom-right corner (bottom, right).
Compute sum by iterating over rectangle.
Update max_sum if sum ≤ k.

Time: O(m²*n²)—all rectangles checked.
Space: O(1)—no extra space.

It’s like brute-forcing every treasure spot!

Comparing the Two Solutions

Prefix Sums with Binary Search (Best):

Time: O(m²*n*log n)—optimized search.
Space: O(n)—prefix sums.
Pros: Fast, scalable.
Cons: More complex.

Brute Force (Alternative):

Time: O(m²*n²)—exhaustive.
Space: O(1)—minimal.
Pros: Simple logic.
Cons: Too slow for large grids.

Binary search wins for efficiency!

Additional Examples and Edge Cases

[[1]], k=2: 1.
Empty matrix: 0.
Negative k: Handles negatives (e.g., k=-5).

Both work, binary search is faster.

Complexity Breakdown

Binary Search:

Time: O(m²*n*log n).
Space: O(n).

Brute Force:

Time: O(m²*n²).
Space: O(1).

Binary search excels for performance.

Key Takeaways

Binary Search: Optimize with prefixes—smart and fast!
Brute Force: Check everything—easy to start!
Grids: 2D challenges are fun.
Python Tip: SortedList rocks—see [Python Basics](/python/basics).

Final Thoughts: Find That Sum

LeetCode 363: Max Sum of Rectangle No Larger Than K in Python is a grid optimization challenge. Prefix sums with binary search is the efficiency champ, while brute force builds understanding. Want more? Try LeetCode 53: Maximum Subarray or LeetCode 304: Range Sum Query 2D. Ready to sum? Visit Solve LeetCode 363 on LeetCode and maximize that rectangle today!