Jobs

Interviews

Discussions

Max Sum of Rectangle No Larger Than K

Hard

Google

2 views

Topics:

ArraysBinary SearchDynamic Programming

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.

For example:

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

Output: 2

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

As another example:

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^5 <= k <= 10^5

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

Max Sum of Rectangle No Larger Than K

Hard

Google

2 views

Topics:

ArraysBinary SearchDynamic Programming

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.

For example:

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

Output: 2

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

As another example:

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^5 <= k <= 10^5

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix? What is the range of values within the matrix and for k?
Is it possible for the matrix to be empty, or for k to be negative?
If there are multiple rectangles that satisfy the condition, should I return the maximum sum among all such rectangles, or can I return any one of them?
If no rectangle has a sum no larger than k, what value should I return?
Does the rectangle have to be a contiguous block of rows and columns, or can the rows and/or columns be non-contiguous?

Brute Force Solution

Approach

The brute-force strategy for this problem is all about trying out every single possible rectangle within the bigger shape. We'll calculate the sum of each rectangle and see if it fits our requirement. It's like trying every single combination until we find the best one.

Here's how the algorithm would work step-by-step:

Consider every possible starting point for the top-left corner of a rectangle.
For each starting point, consider every possible ending point for the bottom-right corner of the rectangle.
Calculate the sum of all the numbers within that rectangle.
Check if the sum is less than or equal to our target value.
If it is, compare it to the largest sum we've seen so far that also meets the requirement.
If this rectangle's sum is larger than our current largest sum but still doesn't exceed the limit, update our largest sum.
Repeat this process for every possible rectangle until we've checked them all.
Finally, return the largest sum we found that was no larger than the target value.

Code Implementation

def max_sub_matrix_no_larger_than_k_brute_force(matrix, k_value):
    max_sum_no_larger_than_k = float('-inf')
    number_of_rows = len(matrix)
    number_of_cols = len(matrix[0])

    for top_row in range(number_of_rows):
        for left_col in range(number_of_cols):
            for bottom_row in range(top_row, number_of_rows):
                for right_col in range(left_col, number_of_cols):
                    rectangle_sum = 0

                    # Calculate the sum of the current rectangle
                    for row in range(top_row, bottom_row + 1):
                        for col in range(left_col, right_col + 1):
                            rectangle_sum += matrix[row][col]

                    # We filter for sums <= k_value
                    if rectangle_sum <= k_value:

                        # Update max_sum if needed
                        max_sum_no_larger_than_k = max(max_sum_no_larger_than_k, rectangle_sum)

    return max_sum_no_larger_than_k

Big(O) Analysis

Time Complexity

O(m²n²) – The algorithm iterates through all possible top-left corners of the rectangle, which takes O(m*n) time where m is the number of rows and n is the number of columns. For each top-left corner, it iterates through all possible bottom-right corners, which also takes O(m*n) time. Therefore, the overall time complexity is O(m*n * m*n) = O(m²n²).

Space Complexity

O(1) – The brute-force approach only requires storing a few scalar variables: starting row and column indices, ending row and column indices, the current rectangle sum, and the maximum sum found so far. The number of these variables remains constant irrespective of the input matrix's size (rows * cols = N). Therefore, the algorithm uses a constant amount of extra space.

Optimal Solution

Approach

The key idea is to efficiently check rectangle sums by pre-calculating sums and using a sorted set data structure. We iterate through all possible pairs of columns to define the rectangle's width, and then use binary search to efficiently find the rectangle's height that gets us as close as possible to the target sum K without exceeding it.

Here's how the algorithm would work step-by-step:

Calculate and store the sum of the numbers in each row for every possible range of columns. This lets us quickly find the sum of any rectangle once we know its top, bottom, left, and right sides.
Go through every possible pair of left and right column boundaries. This defines the width of our rectangle.
For each pair of columns, go row by row and calculate the sum of the rectangle from the top row up to the current row. While calculating this sum, store previous rectangle sums into a sorted set.
While calculating the sum up to the current row, also check if we can subtract a previously calculated sum to get a value close to K. This is done using binary search in the sorted set. If we find such a sum, it means we found a rectangle with a sum close to K.
Keep track of the largest sum found so far that is no larger than K. Update it whenever we find a rectangle with a sum that is closer to K than the current largest sum.
Return the largest rectangle sum that's no larger than K that was found across all column pairs and row combinations.

Code Implementation

from sortedcontainers import SortedSet

def max_sum_submatrix(matrix, target):
    number_of_rows = len(matrix)
    number_of_cols = len(matrix[0]) if number_of_rows > 0 else 0

    max_sum_no_larger_than_k = float('-inf')

    for left_col in range(number_of_cols):
        row_sums = [0] * number_of_rows

        for right_col in range(left_col, number_of_cols):
            for row in range(number_of_rows):
                row_sums[row] += matrix[row][right_col]

            current_sum = 0
            seen_sums = SortedSet([0])

            for row_sum in row_sums:
                current_sum += row_sum
                # Find a prefix sum that gets us closest to target without exceeding
                prefix_sum = current_sum - target

                iterator = seen_sums.lower_bound(prefix_sum)

                if iterator != len(seen_sums):
                    max_sum_no_larger_than_k = max(max_sum_no_larger_than_k, current_sum - seen_sums[iterator])

                seen_sums.add(current_sum)

    return max_sum_no_larger_than_k

Big(O) Analysis

Time Complexity

O(n^2 * m * log(m)) – The algorithm iterates through all possible pairs of columns, resulting in O(n^2) operations where n is the number of columns. For each column pair, it iterates through all rows (m), calculating prefix sums. Inside the row iteration, a binary search operation (log(m)) on a sorted set is performed to find the closest sum to K. Therefore, the overall time complexity is O(n^2 * m * log(m)).

Space Complexity

O(M) – The algorithm utilizes a sorted set to store rectangle sums for each column pair. In the worst-case scenario, the sorted set will store a sum for each row up to the current row, resulting in a maximum size proportional to the number of rows, M. Therefore, the auxiliary space is dominated by the sorted set, contributing O(M) to the space complexity, where M is the number of rows in the input matrix. Other variables used take constant space.

Edge Cases

Case	How to Handle
Null or empty matrix	Return negative infinity as there's no valid rectangle to sum.
K is negative	The problem constraints may disallow this; if allowed, handle negative sums correctly within the algorithm.
Matrix with a single row or single column	Treat the single row/column as a 1D array and apply 1D Kadane-like algorithm with K constraint.
All elements in the matrix are negative and K is positive	Return the largest negative element or negative infinity if all sums exceed K (in negative terms).
K is very large compared to the matrix values, such that the entire matrix sum is less than or equal to K	Efficiently calculate the total sum and return it directly.
Integer overflow when calculating rectangle sums, especially with large matrix dimensions and values	Use long data type to store intermediate rectangle sums to prevent overflow.
The problem has no solution where a sum <= K exists.	Return negative infinity to indicate that no rectangle satisfies the condition.
Maximum-sized matrix that exceeds memory limits when calculating prefix sums.	Instead of precomputing the entire prefix sum, calculate the necessary sums on-the-fly or use a divide-and-conquer strategy to reduce memory usage.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix? What is the range of values within the matrix and for k?
Is it possible for the matrix to be empty, or for k to be negative?
If there are multiple rectangles that satisfy the condition, should I return the maximum sum among all such rectangles, or can I return any one of them?
If no rectangle has a sum no larger than k, what value should I return?
Does the rectangle have to be a contiguous block of rows and columns, or can the rows and/or columns be non-contiguous?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible starting point for the top-left corner of a rectangle.
For each starting point, consider every possible ending point for the bottom-right corner of the rectangle.
Calculate the sum of all the numbers within that rectangle.
Check if the sum is less than or equal to our target value.
If it is, compare it to the largest sum we've seen so far that also meets the requirement.
If this rectangle's sum is larger than our current largest sum but still doesn't exceed the limit, update our largest sum.
Repeat this process for every possible rectangle until we've checked them all.
Finally, return the largest sum we found that was no larger than the target value.

Code Implementation

def max_sub_matrix_no_larger_than_k_brute_force(matrix, k_value):
    max_sum_no_larger_than_k = float('-inf')
    number_of_rows = len(matrix)
    number_of_cols = len(matrix[0])

    for top_row in range(number_of_rows):
        for left_col in range(number_of_cols):
            for bottom_row in range(top_row, number_of_rows):
                for right_col in range(left_col, number_of_cols):
                    rectangle_sum = 0

                    # Calculate the sum of the current rectangle
                    for row in range(top_row, bottom_row + 1):
                        for col in range(left_col, right_col + 1):
                            rectangle_sum += matrix[row][col]

                    # We filter for sums <= k_value
                    if rectangle_sum <= k_value:

                        # Update max_sum if needed
                        max_sum_no_larger_than_k = max(max_sum_no_larger_than_k, rectangle_sum)

    return max_sum_no_larger_than_k

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Calculate and store the sum of the numbers in each row for every possible range of columns. This lets us quickly find the sum of any rectangle once we know its top, bottom, left, and right sides.
Go through every possible pair of left and right column boundaries. This defines the width of our rectangle.
For each pair of columns, go row by row and calculate the sum of the rectangle from the top row up to the current row. While calculating this sum, store previous rectangle sums into a sorted set.
While calculating the sum up to the current row, also check if we can subtract a previously calculated sum to get a value close to K. This is done using binary search in the sorted set. If we find such a sum, it means we found a rectangle with a sum close to K.
Keep track of the largest sum found so far that is no larger than K. Update it whenever we find a rectangle with a sum that is closer to K than the current largest sum.
Return the largest rectangle sum that's no larger than K that was found across all column pairs and row combinations.

Code Implementation

from sortedcontainers import SortedSet

def max_sum_submatrix(matrix, target):
    number_of_rows = len(matrix)
    number_of_cols = len(matrix[0]) if number_of_rows > 0 else 0

    max_sum_no_larger_than_k = float('-inf')

    for left_col in range(number_of_cols):
        row_sums = [0] * number_of_rows

        for right_col in range(left_col, number_of_cols):
            for row in range(number_of_rows):
                row_sums[row] += matrix[row][right_col]

            current_sum = 0
            seen_sums = SortedSet([0])

            for row_sum in row_sums:
                current_sum += row_sum
                # Find a prefix sum that gets us closest to target without exceeding
                prefix_sum = current_sum - target

                iterator = seen_sums.lower_bound(prefix_sum)

                if iterator != len(seen_sums):
                    max_sum_no_larger_than_k = max(max_sum_no_larger_than_k, current_sum - seen_sums[iterator])

                seen_sums.add(current_sum)

    return max_sum_no_larger_than_k

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return negative infinity as there's no valid rectangle to sum.
K is negative	The problem constraints may disallow this; if allowed, handle negative sums correctly within the algorithm.
Matrix with a single row or single column	Treat the single row/column as a 1D array and apply 1D Kadane-like algorithm with K constraint.
All elements in the matrix are negative and K is positive	Return the largest negative element or negative infinity if all sums exceed K (in negative terms).
K is very large compared to the matrix values, such that the entire matrix sum is less than or equal to K	Efficiently calculate the total sum and return it directly.
Integer overflow when calculating rectangle sums, especially with large matrix dimensions and values	Use long data type to store intermediate rectangle sums to prevent overflow.
The problem has no solution where a sum <= K exists.	Return negative infinity to indicate that no rectangle satisfies the condition.
Maximum-sized matrix that exceeds memory limits when calculating prefix sums.	Instead of precomputing the entire prefix sum, calculate the necessary sums on-the-fly or use a divide-and-conquer strategy to reduce memory usage.