363. Max Sum of Rectangle No Larger Than K


Problem Description

Given a 2D grid called matrix, with dimensions m x n, and an integer k, the problem asks to find the maximum sum of any rectangle within the matrix, where the sum must not exceed k. A rectangle in a matrix is defined by any contiguous block forming an area within the grid. The sum of a rectangle is simply the sum of all the elements it contains. We have the guarantee that there exists at least one such rectangle whose sum is no more than k.

Intuition

The significant complexity in solving this problem lies in dealing with two dimensions while trying to optimize for the sum condition. A common approach to problems involving subarray sums is to use a running total and consider differences of this cumulative sum to find subarrays that match certain criteria; however, that typically applies to one-dimensional arrays.

When extending this idea to two dimensions, one efficient method is to reduce the problem to a one-dimensional problem by fixing one dimension. We do this by selecting two rows at a time and then compressing those rows into a one-dimensional array where each element is the sum of the elements in the column between the two rows. This effectively converts the problem into the "Maximum Sum of Subarray No More Than K" for a one-dimensional array.

Once we have this one-dimensional array, we can use a cumulative sum array to store previous sums and a sorted set to efficiently check if there's a previous sum that, when subtracted from the current sum, gives a result that is as close to k as possible but not greater. The SortedSet in Python comes in handy because it maintains the elements in sorted order, allowing binary-search-like operations for finding the appropriate sums we're interested in. This is a classic case of using space to gain time: we're collecting possible sums in the sorted set at the expense of memory in order to save significant time on searching.

The used algorithm iterates over all possible pairs of rows, for each pair compresses them into a one-dimensional array, computes a running total for that array, and searches the sorted set to find the best match for the current running total that does not exceed k. The maximum of these matches is remembered as it represents the maximum sum rectangle for the chosen rows. This is repeated until all pairs of rows have been considered, and the overall maximum sum that does not exceed k is the solution to the problem.

Learn more about Binary Search and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Solution Approach

The solution uses a few techniques and data structures. Let's walk through the steps and the rationale behind them:

  1. Two-pointer Technique: We iterate over all possible row pairs using two pointers: the outer loop variable i starting from the first row and the inner loop variable j ranging from i to the last row. This generates all combinations of row starts and ends for our rectangles.

  2. Cumulative Column Sums: For each row pair (i, j), we compute the cumulative sum for each column in this section of the matrix. We maintain a one-dimensional array nums, where nums[h] represents the sum of elements from row i to j in column h. This collapses our two-dimensional problem into a one-dimensional array problem.

  3. Prefix Sum and Sorted Set: We create a variable s representing the cumulative sum as we iterate through nums and a SortedSet ts to store past cumulative sums. The sorted set allows us to effectively perform two crucial operations: adding a new cumulative sum and searching for a particular sum. We start with a zero in the set because that represents an empty rectangle, which conceptually aligns with having no rectangle at all (a sum of zero).

  4. Finding the Best Subarray Sum: As we get the cumulative sum s, we're interested in finding some previous sum in our set ts such that the difference s - previous_sum is as close to k as possible without going over. To do this, we look for the smallest prefix sum in the set where the s - prefix_sum is still larger than k. We find this prefix using the function ts.bisect_left(s - k), which does a binary search for the position where s - k could be inserted while maintaining order. This position points to the smallest number larger or equal to s - k.

  5. Maximizing the Subarray Sum: After finding such a prefix sum (ts[p]), we check if the difference s - ts[p] is larger than our previously recorded answer but still not larger than k and update our answer ans accordingly.

This process repeats until all row combinations have been exhausted and the ans variable holds the maximum rectangle sum no larger than k.

The algorithm runs in O(m^2 * n * log(n)) time, where m is the number of rows and n is the number of columns. This complexity comes from the fact that there are O(m^2) row pairs, for each of which we go through n columns and perform a log(n) operation (binary search) in the sorted set for each one.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's walk through the solution using a small example. Suppose we have the following 3x3 matrix and k = 8:

1matrix = [
2  [1, 0, 1],
3  [0, -2, 3],
4  [1, 2, -1]
5]

Our goal is to find the maximum sum of any rectangle in this matrix that does not exceed k.

Step 1: Two-pointer Technique
We'll consider all possible pairs of rows in the matrix. For simplicity, let's look at the pair where the first row has index i = 0 and the second row has index j = 2. This will cover the entire height of the matrix.

Step 2: Cumulative Column Sums
We combine rows 0 to 2 into a single one-dimensional array, summing them column-wise:

1nums = [
2  (matrix[0][0] + matrix[1][0] + matrix[2][0]),    // First column sum
3  (matrix[0][1] + matrix[1][1] + matrix[2][1]),    // Second column sum
4  (matrix[0][2] + matrix[1][2] + matrix[2][2])     // Third column sum
5]
6
7nums = [1, 0, 3]     // Columns summed between rows 0 and 2

Step 3: Prefix Sum and Sorted Set
We set s = 0 and start with an empty SortedSet ts = {0} to store cumulatively the sums.

Step 4: Finding the Best Subarray Sum
As we go through the array nums, we add the element to s and search for the best subarray sum:

  • For the first column, s = 1, we look for the smallest number in {0} such that when subtracted from s doesn't exceed k. The best we can do is s - 0 = 1 which is less than 8 (our k).

  • Now, we add s to our sorted set: ts = {0, 1}.

  • Then for the second column, s becomes 1. There is no change since nums[1] is 0, so the potential sums are identical to the previous step.

  • Next, for the third column, s becomes 1 + 3 = 4. We look for the smallest number in {0, 1} such that 4 - num is as close as possible to k without going over. In both cases, we are under k.

With every addition to s, we continue checking the sorted set ts for the best possible subarray sum, remembering to add s to ts each time to consider it for future subarrays.

Step 5: Maximizing the Subarray Sum
We continue the above process until all column sums for the current row pair are considered. The largest sum we can achieve without exceeding k is the one we aim for. In our small example, considering all the combinations, the maximum sum we should find under or equal to k is 4.

By repeating Steps 1 to 5 for all row pairs (i, j), we exhaust all possible rectangles in the matrix, and ans is updated each time we find a larger sum that is within our constraint of k. In this case, after considering all possible rectangles, we find that the maximum sum that does not exceed k is 4, which comes from the sub-matrix:

1[1, 0, 1]
2[0, -2, 3]
3[1, 2, -1]

This is just a simple example that demonstrates the method; in a larger matrix with more variable elements, the sorted set would play a more significant role in efficiently finding the possible rectangle sums.

Solution Implementation

1from sortedcontainers import SortedSet
2from math import inf
3
4class Solution:
5    def max_sum_submatrix(self, matrix, k):
6        # Number of rows and columns in the matrix
7        num_rows, num_cols = len(matrix), len(matrix[0])
8        # This variable will store the maximum sum of the submatrix that doesn't exceed 'k'
9        max_sum = -inf
10
11        # Iterate over the starting row of our submatrix
12        for starting_row in range(num_rows):
13            # A list to store row sums
14            row_sums = [0] * num_cols
15
16            # Iterate over the ending row of our submatrix
17            for ending_row in range(starting_row, num_rows):
18                # Update the row sums by adding corresponding values from the new row
19                for col in range(num_cols):
20                    row_sums[col] += matrix[ending_row][col]
21
22                # Initialize current sum and create a sorted set to store prefix sums
23                current_sum = 0
24                sorted_prefix_sums = SortedSet([0])
25              
26                # Iterating over the cumulative sum of row elements
27                for sum_value in row_sums:
28                    current_sum += sum_value
29                    # Find the index of the smallest prefix sum so that
30                    # current_sum - prefix_sum <= k and we get the biggest current_sum possible
31                    index = sorted_prefix_sums.bisect_left(current_sum - k)
32                    # If such index exists in the sorted set, update the max_sum
33                    if index != len(sorted_prefix_sums):
34                        max_sum = max(max_sum, current_sum - sorted_prefix_sums[index])
35                    # Add the current prefix sum to the sorted set
36                    sorted_prefix_sums.add(current_sum)
37
38        # Return the maximum sum found that is less than or equal to 'k'
39        return max_sum
40
1class Solution {
2    public int maxSumSubmatrix(int[][] matrix, int k) {
3        int rows = matrix.length;
4        int cols = matrix[0].length;
5        final int infinity = Integer.MAX_VALUE;
6        int maxSum = -infinity;
7        // Iterating over the starting row for submatrix
8        for (int startRow = 0; startRow < rows; ++startRow) {
9            int[] columnSums = new int[cols];
10            // Extending the submatrix to each possible end row
11            for (int endRow = startRow; endRow < rows; ++endRow) {
12                // Summing up each column element of the current submatrix
13                for (int col = 0; col < cols; ++col) {
14                    columnSums[col] += matrix[endRow][col];
15                }
16                int currentSum = 0;
17                TreeSet<Integer> set = new TreeSet<>();
18                // Adding a base to consider subarrays starting from the first element
19                set.add(0);
20                // Traversing the cumulative column sums to find the submatrix with the sum closest to k
21                for (int sum : columnSums) {
22                    currentSum += sum;
23                    // Checking if there is a prefix sum that, if removed, leaves a sum close to k
24                    Integer minSum = set.ceiling(currentSum - k);
25                    if (minSum != null) {
26                        maxSum = Math.max(maxSum, currentSum - minSum);
27                    }
28                    set.add(currentSum);
29                }
30            }
31        }
32        return maxSum;
33    }
34}
35
1class Solution {
2public:
3    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
4        // Get the number of rows and columns in the matrix
5        int rowCount = matrix.size(), colCount = matrix[0].size();
6        // Initialize the answer with the smallest integer value
7        const int INF = INT_MIN; // INT_MIN is from climits and more standard than 1 << 30
8        int maxSum = INF;
9      
10        // Outer loop - Start of the row to consider for submatrices
11        for (int rowStart = 0; rowStart < rowCount; ++rowStart) {
12            // Initialize an array to store the sum of elements in current submatrix columns
13            vector<int> columnSums(colCount, 0);
14            // Inner loop - End of the row to consider for submatrices
15            for (int rowEnd = rowStart; rowEnd < rowCount; ++rowEnd) {
16                // Sum up the column elements in the current submatrix
17                for (int col = 0; col < colCount; ++col) {
18                    columnSums[col] += matrix[rowEnd][col];
19                }
20                // Use a set to help us find the rectangle with max sum not exceed k
21                set<int> accumulatedSums;
22                // Start with zero as an accumulated sum to compare
23                accumulatedSums.insert(0);
24                // Initialize the sum for the current submatrix
25                int currSum = 0;
26                // Iterate through each column sum
27                for (int sum : columnSums) {
28                    currSum += sum;
29                    // Find the smallest number in accumulatedSums such that: number >= currSum - k
30                    auto it = accumulatedSums.lower_bound(currSum - k);
31                    // If such a number is found, update maxSum if necessary
32                    if (it != accumulatedSums.end()) {
33                        maxSum = max(maxSum, currSum - *it);
34                    }
35                    // Add the current sum to the set of accumulated sums
36                    accumulatedSums.insert(currSum);
37                }
38            }
39        }
40        // Return the maximum submatrix sum such that it does not exceed k
41        return maxSum;
42    }
43};
44
1// Defines a comparator type that compares two items and returns a number.
2type Compare<T> = (lhs: T, rhs: T) => number;
3
4// Represents a node in a red-black tree with added functionality.
5interface RBTreeNode<T = number> {
6  data: T;
7  count: number;
8  left: RBTreeNode<T> | null;
9  right: RBTreeNode<T> | null;
10  parent: RBTreeNode<T> | null;
11  color: number;
12}
13
14// Helper function to determine if a given node is on the left of its parent.
15function isOnLeft<T>(node: RBTreeNode<T>): boolean {
16  return node === node.parent!.left;
17}
18
19// Helper function to check if a node has a red child.
20function hasRedChild<T>(node: RBTreeNode<T>): boolean {
21  return !!((node.left && node.left.color === 0) || (node.right && node.right.color === 0));
22}
23
24// Helper function to rotate a given node to the left.
25// ...
26
27// Helper function to rotate a given node to the right.
28// ...
29
30// Helper function to swap colors between two nodes.
31// ...
32
33// Helper function to swap data between two nodes.
34// ...
35
36// ... Other necessary RBTree methods ...
37
38// Implements the red-black tree.
39function createRBTree<T>(compare: Compare<T>): RBTreeNode<T> | null {
40  let root: RBTreeNode<T> | null = null;
41  // Implement the methods of RBTree (insert, delete, find, rotations, etc.) here.
42  // ...
43  return root;
44}
45
46// ... Other necessary TreeSet and TreeMultiSet methods ...
47
48// Represents a collection of unique elements with a defined order.
49function createTreeSet<T>(collection: T[] = [], compare: Compare<T>): TreeSet<T> {
50  const tree: RBTreeNode<T> | null = createRBTree(compare);
51  // Functionality to support Tree operations like add, delete, find, etc.
52  // ...
53  return {} as TreeSet<T>; // Replace with actual TreeSet implementation.
54}
55
56// Represents a collection that allows duplicates and has a defined order.
57function createTreeMultiSet<T>(collection: T[] = [], compare: Compare<T>): TreeMultiSet<T> {
58  const tree: RBTreeNode<T> | null = createRBTree(compare);
59  // Functionality to support MultiSet operations like add, delete, count, etc.
60  // ...
61  return {} as TreeMultiSet<T>; // Replace with actual TreeMultiSet implementation.
62}
63
64// Computes the max sum of a rectangle in the matrix that does not exceed `k`.
65function maxSumSubmatrix(matrix: number[][], k: number): number {
66  const m = matrix.length;
67  const n = matrix[0].length;
68  let maxSum = -Infinity;
69
70  // Computes cumulative sum for submatrices and uses TreeSet to find
71  // subrectangle with the largest sum that doesn't exceed `k`.
72  for (let i = 0; i < m; ++i) {
73    const cumulativeSum: number[] = new Array(n).fill(0);
74
75    for (let j = i; j < m; ++j) {
76      // Update the cumulative sum by adding the new row's elements.
77      for (let h = 0; h < n; ++h) {
78        cumulativeSum[h] += matrix[j][h];
79      }
80
81      // Use TreeSet to compute the maximum sum subrectangle within `k`.
82      const treeSet: TreeSet<number> = createTreeSet<number>([], (lhs, rhs) => lhs - rhs);
83      // ... Perform the necessary TreeSet operations ...
84
85      // Update the maximum sum found so far.
86      // ...
87    }
88  }
89
90  return maxSum;
91}
92
93// Define additional methods and variables here that are necessary for the global implementation.
94// ...
95
Not Sure What to Study? Take the 2-min Quiz:

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

Time and Space Complexity

The given code implements an algorithm to find the maximum sum of a submatrix in a 2D array that is no larger than k. Here's the analysis of its time and space complexity:

Time Complexity

  • There are two nested loops (loop over i and j) that iterate over the rows of the matrix. In the worst case, both loops iterate m times, where m is the number of rows. This part contributes O(m^2) to the time complexity.
  • Inside the nested loops, there's another loop over h that iterates n times where n is the number of columns, to sum up the elements in the current rectangle (nums). This loop runs n times for each iteration of the outer two loops, adding an O(m^2 * n) factor.
  • For each nums subarray created, we perform a binary search and insertion into a sorted set ts. The SortedSet operations are logarithmic with respect to the size of the set. The set could potentially contain up to n elements in the worst case, so each operation (bisect_left and add) will take O(log n). As these sorted set operations are done for each element in nums, this results in an additional O(n log n) term.
  • Combining the factors, the overall time complexity is O(m^2 * n * n * log n) = O(m^2 * n^2 * log n).

Space Complexity

  • The space complexity is mainly determined by the space needed to store the nums array and the sorted set ts.
  • The array nums has a size of n, so it contributes O(n) to the space complexity.
  • The sorted set ts can contain up to n prefix sums, contributing another O(n) to the space complexity.
  • As these are the largest allocations and no other allocations grow with respect to m or n, the total space complexity is O(n).

In conclusion, the time complexity of the code is O(m^2 * n^2 * log n) and the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫