Jobs

Interviews

Discussions

Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Medium

Asked by:

123 views

Topics:

ArraysDynamic ProgrammingBinary Search

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10⁴
0 <= threshold <= 10⁵

Try coding it in LeetCode

Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Medium

Asked by:

123 views

Topics:

ArraysDynamic ProgrammingBinary Search

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10⁴
0 <= threshold <= 10⁵

Try coding it in LeetCode

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 constraints on the dimensions of the matrix `mat` (number of rows and columns), and what are the possible ranges for the integer values within the matrix?
Can the `threshold` value be negative, zero, or very large?
Is it possible for the input matrix `mat` to be empty, or have zero rows or columns?
What should be returned if no square with a sum less than or equal to the `threshold` can be found, even for a 1x1 square?
Are all elements in the matrix guaranteed to be positive, or can they be zero or negative?

Brute Force Solution

Approach

The brute force approach involves checking every possible square that could fit within the given grid. For each potential square, we calculate the sum of all the numbers inside it and see if that sum is within the allowed limit.

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

Consider every single spot in the grid as a potential top-left corner of a square.
From each potential corner, try making squares of all possible sizes, starting with a tiny 1x1 square and getting bigger.
For each square you imagine, add up all the numbers within its boundaries.
Compare this total sum to the maximum allowed sum. If the sum is too big, this square size is not a valid option from this corner.
If the sum is within the limit, remember the size of this valid square.
After checking all possible square sizes from all possible starting corners, look at all the valid square sizes you found.
The answer is the largest side length among all the valid squares you identified.

Code Implementation

def max_side_length_brute_force(mat, threshold):
    rows_in_grid = len(mat)
    columns_in_grid = len(mat[0])
    maximum_side_found = 0

    # Iterate through every possible top-left corner of a square
    for top_row_index in range(rows_in_grid):
        for left_column_index in range(columns_in_grid):
            # Try all possible square sizes from this corner
            for side_length in range(1, min(rows_in_grid - top_row_index, columns_in_grid - left_column_index) + 1):
                bottom_row_index = top_row_index + side_length - 1
                right_column_index = left_column_index + side_length - 1
                current_square_sum = 0

                # Calculate the sum of elements within the current square
                for row_to_sum in range(top_row_index, bottom_row_index + 1):
                    for column_to_sum in range(left_column_index, right_column_index + 1):
                        current_square_sum += mat[row_to_sum][column_to_sum]

                # Check if the sum is within the threshold
                if current_square_sum <= threshold:
                    # Update the maximum side length if this square is valid and larger
                    maximum_side_found = max(maximum_side_found, side_length)

    return maximum_side_found

Big(O) Analysis

Time Complexity

O(m^3 * n^3) – Let the input grid have dimensions m rows and n columns. The brute force approach iterates through every possible top-left corner of a square, which takes O(m*n) time. For each corner, it then iterates through all possible square sizes, up to min(m, n). Calculating the sum of each square naively takes O(side^2) time, where 'side' is the current side length. In the worst case, side can be up to min(m,n). Thus, the total complexity is O(m * n * min(m, n) * min(m, n)^2), which simplifies to O(m^3 * n^3) assuming m and n are of similar magnitude.

Space Complexity

O(1) – The described brute force approach primarily uses a few variables to keep track of the current square's top-left corner, its side length, and the running sum of its elements. It does not create any auxiliary data structures whose size depends on the input grid dimensions. Therefore, the auxiliary space complexity is constant, O(1), as the memory usage does not scale with the size of the input grid.

Optimal Solution

Approach

The problem asks for the largest square within a grid where the sum of all the numbers inside that square is no more than a given limit. The smart approach involves pre-calculating sums of rectangular areas to quickly find the sum of any square, and then efficiently searching for the largest possible square.

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

First, imagine creating a helper grid that stores the sum of all numbers from the very top-left corner up to each specific spot in the original grid. This allows us to quickly find the sum of any rectangular section.
Now, think about checking potential squares. Instead of checking every single possible square size and position from scratch, we can be more efficient.
We can try to find the largest possible square size that might work. For a given square size, we can quickly check if there's any square of that size in the grid whose numbers sum up to less than or equal to our limit, using the pre-calculated sums.
If we can find a square of a certain size that meets the condition, we know we might be able to find an even larger one. If we can't find a square of that size, we know we need to look for smaller ones.
This suggests a search strategy: we can efficiently determine the largest square size that satisfies the sum condition by trying different sizes and seeing if they work. This is like a guessing game where we narrow down the possibilities.
Once we've found the largest possible side length for a valid square, that's our answer.

Code Implementation

def maximum_side_length(matrix, threshold):
    rows_in_matrix = len(matrix)
    columns_in_matrix = len(matrix[0])

    # Pre-calculate prefix sums to quickly query rectangular sums.
    prefix_sum_grid = [[0] * (columns_in_matrix + 1) for _ in range(rows_in_matrix + 1)]
    for row_index in range(rows_in_matrix):
        for column_index in range(columns_in_matrix):
            prefix_sum_grid[row_index + 1][column_index + 1] = (
                matrix[row_index][column_index]
                + prefix_sum_grid[row_index][column_index + 1]
                + prefix_sum_grid[row_index + 1][column_index]
                - prefix_sum_grid[row_index][column_index]
            )

    def get_square_sum(row, col, side_length):
        # Efficiently calculate sum of a square using prefix sums.
        bottom_row = row + side_length
        right_column = col + side_length
        return (
            prefix_sum_grid[bottom_row][right_column]
            - prefix_sum_grid[row][right_column]
            - prefix_sum_grid[bottom_row][col]
            + prefix_sum_grid[row][col]
        )

    def can_form_square(side_length):
        # Check if any square of the given side_length meets the threshold.
        for row_index in range(rows_in_matrix - side_length + 1):
            for column_index in range(columns_in_matrix - side_length + 1):
                if get_square_sum(row_index, column_index, side_length) <= threshold:
                    return True
        return False

    # Binary search for the largest possible side length.
    low_side = 0
    high_side = min(rows_in_matrix, columns_in_matrix)
    maximum_valid_side = 0

    while low_side <= high_side:
        mid_side = (low_side + high_side) // 2
        if mid_side == 0:
            # A square of side 0 is always possible and has sum 0.
            low_side = mid_side + 1
            continue
        if can_form_square(mid_side):
            # If a square of mid_side works, try for a larger one.
            maximum_valid_side = mid_side
            low_side = mid_side + 1
        else:
            # If a square of mid_side does not work, we need a smaller one.
            high_side = mid_side - 1

    return maximum_valid_side

Big(O) Analysis

Time Complexity

O(m*n*min(m,n)) – The pre-computation of prefix sums takes O(m*n) time, where m is the number of rows and n is the number of columns. The core of the efficient solution involves a binary search for the side length of the square. For each potential side length tested during the binary search, we iterate through all possible top-left corners of a square of that size. This check for a given side length k involves iterating through roughly (m-k+1)*(n-k+1) positions. The binary search performs log(min(m,n)) iterations. Therefore, the total time complexity is O(m*n + min(m,n) * m * n), which simplifies to O(m*n*min(m,n)).

Space Complexity

O(M*N) – The primary auxiliary space is used to create a helper grid (often called a prefix sum or integral image) which has the same dimensions as the input grid, say M rows and N columns. This grid stores the cumulative sums of rectangular areas, allowing for O(1) sum queries. No other significant auxiliary data structures are introduced that scale with the input size.

Edge Cases

Case	How to Handle
Empty or null matrix input	The solution should handle null or empty matrix inputs by returning 0 as no square can be formed.
Matrix with a single element	If the single element is less than or equal to the threshold, the maximum side length is 1, otherwise it's 0.
Matrix dimensions are 1xN or Nx1	The logic should correctly identify that only 1x1 squares are possible in such cases.
Threshold is very small (e.g., negative or zero)	If the threshold is non-positive, and all matrix elements are positive, no valid square will exist, and the result should be 0.
All elements in the matrix are zero	Any square size is valid if the threshold is non-negative; the maximum possible side length should be returned.
All elements in the matrix are very large	If even a 1x1 square's sum exceeds the threshold, the answer must be 0.
No square satisfies the threshold condition	The algorithm should correctly determine that no valid square exists and return 0.
The entire matrix forms a valid square	The algorithm should be able to find the maximum side length equal to the minimum dimension of the matrix if the whole matrix sum is within the threshold.

Empty or null matrix input

How to Handle:

The solution should handle null or empty matrix inputs by returning 0 as no square can be formed.

Matrix with a single element

How to Handle:

If the single element is less than or equal to the threshold, the maximum side length is 1, otherwise it's 0.

Matrix dimensions are 1xN or Nx1

How to Handle:

The logic should correctly identify that only 1x1 squares are possible in such cases.

Threshold is very small (e.g., negative or zero)

How to Handle:

If the threshold is non-positive, and all matrix elements are positive, no valid square will exist, and the result should be 0.

All elements in the matrix are zero

How to Handle:

Any square size is valid if the threshold is non-negative; the maximum possible side length should be returned.

All elements in the matrix are very large

How to Handle:

If even a 1x1 square's sum exceeds the threshold, the answer must be 0.

No square satisfies the threshold condition

How to Handle:

The algorithm should correctly determine that no valid square exists and return 0.

The entire matrix forms a valid square

How to Handle:

The algorithm should be able to find the maximum side length equal to the minimum dimension of the matrix if the whole matrix sum is within the threshold.

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 constraints on the dimensions of the matrix `mat` (number of rows and columns), and what are the possible ranges for the integer values within the matrix?
Can the `threshold` value be negative, zero, or very large?
Is it possible for the input matrix `mat` to be empty, or have zero rows or columns?
What should be returned if no square with a sum less than or equal to the `threshold` can be found, even for a 1x1 square?
Are all elements in the matrix guaranteed to be positive, or can they be zero or negative?

Brute Force Solution

Approach

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

Consider every single spot in the grid as a potential top-left corner of a square.
From each potential corner, try making squares of all possible sizes, starting with a tiny 1x1 square and getting bigger.
For each square you imagine, add up all the numbers within its boundaries.
Compare this total sum to the maximum allowed sum. If the sum is too big, this square size is not a valid option from this corner.
If the sum is within the limit, remember the size of this valid square.
After checking all possible square sizes from all possible starting corners, look at all the valid square sizes you found.
The answer is the largest side length among all the valid squares you identified.

Code Implementation

def max_side_length_brute_force(mat, threshold):
    rows_in_grid = len(mat)
    columns_in_grid = len(mat[0])
    maximum_side_found = 0

    # Iterate through every possible top-left corner of a square
    for top_row_index in range(rows_in_grid):
        for left_column_index in range(columns_in_grid):
            # Try all possible square sizes from this corner
            for side_length in range(1, min(rows_in_grid - top_row_index, columns_in_grid - left_column_index) + 1):
                bottom_row_index = top_row_index + side_length - 1
                right_column_index = left_column_index + side_length - 1
                current_square_sum = 0

                # Calculate the sum of elements within the current square
                for row_to_sum in range(top_row_index, bottom_row_index + 1):
                    for column_to_sum in range(left_column_index, right_column_index + 1):
                        current_square_sum += mat[row_to_sum][column_to_sum]

                # Check if the sum is within the threshold
                if current_square_sum <= threshold:
                    # Update the maximum side length if this square is valid and larger
                    maximum_side_found = max(maximum_side_found, side_length)

    return maximum_side_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, imagine creating a helper grid that stores the sum of all numbers from the very top-left corner up to each specific spot in the original grid. This allows us to quickly find the sum of any rectangular section.
Now, think about checking potential squares. Instead of checking every single possible square size and position from scratch, we can be more efficient.
We can try to find the largest possible square size that might work. For a given square size, we can quickly check if there's any square of that size in the grid whose numbers sum up to less than or equal to our limit, using the pre-calculated sums.
If we can find a square of a certain size that meets the condition, we know we might be able to find an even larger one. If we can't find a square of that size, we know we need to look for smaller ones.
This suggests a search strategy: we can efficiently determine the largest square size that satisfies the sum condition by trying different sizes and seeing if they work. This is like a guessing game where we narrow down the possibilities.
Once we've found the largest possible side length for a valid square, that's our answer.

Code Implementation

def maximum_side_length(matrix, threshold):
    rows_in_matrix = len(matrix)
    columns_in_matrix = len(matrix[0])

    # Pre-calculate prefix sums to quickly query rectangular sums.
    prefix_sum_grid = [[0] * (columns_in_matrix + 1) for _ in range(rows_in_matrix + 1)]
    for row_index in range(rows_in_matrix):
        for column_index in range(columns_in_matrix):
            prefix_sum_grid[row_index + 1][column_index + 1] = (
                matrix[row_index][column_index]
                + prefix_sum_grid[row_index][column_index + 1]
                + prefix_sum_grid[row_index + 1][column_index]
                - prefix_sum_grid[row_index][column_index]
            )

    def get_square_sum(row, col, side_length):
        # Efficiently calculate sum of a square using prefix sums.
        bottom_row = row + side_length
        right_column = col + side_length
        return (
            prefix_sum_grid[bottom_row][right_column]
            - prefix_sum_grid[row][right_column]
            - prefix_sum_grid[bottom_row][col]
            + prefix_sum_grid[row][col]
        )

    def can_form_square(side_length):
        # Check if any square of the given side_length meets the threshold.
        for row_index in range(rows_in_matrix - side_length + 1):
            for column_index in range(columns_in_matrix - side_length + 1):
                if get_square_sum(row_index, column_index, side_length) <= threshold:
                    return True
        return False

    # Binary search for the largest possible side length.
    low_side = 0
    high_side = min(rows_in_matrix, columns_in_matrix)
    maximum_valid_side = 0

    while low_side <= high_side:
        mid_side = (low_side + high_side) // 2
        if mid_side == 0:
            # A square of side 0 is always possible and has sum 0.
            low_side = mid_side + 1
            continue
        if can_form_square(mid_side):
            # If a square of mid_side works, try for a larger one.
            maximum_valid_side = mid_side
            low_side = mid_side + 1
        else:
            # If a square of mid_side does not work, we need a smaller one.
            high_side = mid_side - 1

    return maximum_valid_side

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null matrix input	The solution should handle null or empty matrix inputs by returning 0 as no square can be formed.
Matrix with a single element	If the single element is less than or equal to the threshold, the maximum side length is 1, otherwise it's 0.
Matrix dimensions are 1xN or Nx1	The logic should correctly identify that only 1x1 squares are possible in such cases.
Threshold is very small (e.g., negative or zero)	If the threshold is non-positive, and all matrix elements are positive, no valid square will exist, and the result should be 0.
All elements in the matrix are zero	Any square size is valid if the threshold is non-negative; the maximum possible side length should be returned.
All elements in the matrix are very large	If even a 1x1 square's sum exceeds the threshold, the answer must be 0.
No square satisfies the threshold condition	The algorithm should correctly determine that no valid square exists and return 0.
The entire matrix forms a valid square	The algorithm should be able to find the maximum side length equal to the minimum dimension of the matrix if the whole matrix sum is within the threshold.

Empty or null matrix input

How to Handle:

The solution should handle null or empty matrix inputs by returning 0 as no square can be formed.

Matrix with a single element

How to Handle:

If the single element is less than or equal to the threshold, the maximum side length is 1, otherwise it's 0.

Matrix dimensions are 1xN or Nx1

How to Handle:

The logic should correctly identify that only 1x1 squares are possible in such cases.

Threshold is very small (e.g., negative or zero)

How to Handle:

If the threshold is non-positive, and all matrix elements are positive, no valid square will exist, and the result should be 0.

All elements in the matrix are zero

How to Handle:

Any square size is valid if the threshold is non-negative; the maximum possible side length should be returned.

All elements in the matrix are very large

How to Handle:

If even a 1x1 square's sum exceeds the threshold, the answer must be 0.

No square satisfies the threshold condition

How to Handle:

The algorithm should correctly determine that no valid square exists and return 0.

The entire matrix forms a valid square

How to Handle:

The algorithm should be able to find the maximum side length equal to the minimum dimension of the matrix if the whole matrix sum is within the threshold.