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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 3338

Difficulty: Medium

Paid? No

Companies: Barclays

Problem Description

Given a 0-indexed integer matrix grid and an integer k, count the number of submatrices that contain the top-left element of grid (i.e. submatrices that start at (0,0)) and have a sum less than or equal to k.

Key Insights

  • Only submatrices that include the top-left element (0,0) are considered. This means every valid submatrix can be uniquely defined by its bottom-right corner (i, j).
  • The sum of the submatrix from (0,0) to (i,j) can be efficiently computed using a 2D prefix sum (cumulative sum) matrix.
  • Given the constraints and non-negativity of grid elements, we can compute these prefix sums in O(m*n) time and simply count those that meet the requirement.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

The solution leverages a 2D prefix sum array to compute the sum of the submatrix from the top-left element (0,0) to any point (i,j) in constant time after preprocessing. The prefix sum for cell (i, j) is computed as: prefix[i][j] = grid[i][j] + (prefix[i-1][j] if i > 0 else 0) + (prefix[i][j-1] if j > 0 else 0) - (prefix[i-1][j-1] if i > 0 and j > 0 else 0) Then, iterate over all cells and count the number of positions where prefix[i][j] <= k.

Code Solutions

# Python solution for counting submatrices with top-left element and sum <= k

def countSubmatricesWithTopLeft(grid, k):
    # Get the dimensions of the grid
    m, n = len(grid), len(grid[0])
    # Initialize a 2D prefix sum array with the same dimensions as grid
    prefix = [[0] * n for _ in range(m)]
    count = 0

    for i in range(m):
        for j in range(n):
            # Compute the prefix sum for the current cell (i, j)
            top = prefix[i-1][j] if i > 0 else 0
            left = prefix[i][j-1] if j > 0 else 0
            diagonal = prefix[i-1][j-1] if i > 0 and j > 0 else 0
            prefix[i][j] = grid[i][j] + top + left - diagonal

            # If the submatrix sum is within the allowed value, increment the count
            if prefix[i][j] <= k:
                count += 1

    return count

# Example usage:
grid1 = [[7,6,3],[6,6,1]]
k1 = 18
print(countSubmatricesWithTopLeft(grid1, k1))  # Expected output: 4
← Back to All Questions