Skip to main content
Talentd

Max Sum of Rectangle No Larger Than K - Solution & Explanation

HardArrayBinary SearchMatrixPrefix Sum24 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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
  • -105 <= k <= 105

 

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.

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.

Code

PythonC++

Python

C++

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.

The C solution initializes a memo array to store intermediate results. The solve function checks if the value is already computed to avoid recalculating it, and recursively calculates values as needed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) due to the memoization array

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.

The C solution iteratively calculates Fibonacci numbers using constant space, which makes it efficient for larger values of n.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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) due to the memoization array

Iterative Approach

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

Enumerate Boundaries + Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sum with IterationO(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 MemoizationO(m * n * states)O(m * n)Useful for conceptual exploration or smaller input sizes

Video Solution

Max Sum of Rectangle No Larger Than K | Leetcode 363 | Live coding session • Coding Decoded • 13,381 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Max Sum of Rectangle No Larger Than K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays