We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Submatrices with Top-Left Element and Sum Less Than k

Difficulty: Medium

Problem Description

You are given a 0-indexed integer matrix grid and an integer k. Return the number of submatrices that contain the top-left element of the grid, and have a sum less than or equal to k.

Key Insights

  • Only submatrices that include the top-left element (grid[0][0]) need to be considered.
  • The problem can be approached using a prefix sum technique to efficiently calculate the sum of various submatrices.
  • By iterating over possible bottom-right corners of the submatrices, we can maintain a running sum and check against k.

Space and Time Complexity

Time Complexity: O(m * n^2) - where m is the number of rows and n is the number of columns, since we iterate through potential bottom-right corners while maintaining sums. Space Complexity: O(n) - for storing cumulative sums.

Solution

To solve the problem, we can use a combination of prefix sums and a nested loop approach. We first compute the prefix sum of the grid to allow for quick sum calculations of any submatrix. Then, we iterate over all possible bottom-right corners of the submatrices that start from the top-left element and count how many of these have a sum that is less than or equal to k.

Code Solutions

def countSubmatrices(grid, k):
    m, n = len(grid), len(grid[0])
    count = 0
    
    # Create a prefix sum array
    prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix_sum[i][j] = grid[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]
    
    # Iterate over all possible bottom-right corners of submatrices
    for rowEnd in range(1, m + 1):
        for colEnd in range(1, n + 1):
            # Calculate the sum of the submatrix from (0, 0) to (rowEnd-1, colEnd-1)
            total = prefix_sum[rowEnd][colEnd]
            if total <= k:
                count += 1
    
    return count
← Back to All Questions