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

Find Sorted Submatrices With Maximum Element at Most K

Number: 3652

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given an m x n matrix grid and a non‐negative integer k, count the number of submatrices (i.e. contiguous blocks in the grid) that satisfy both of the following:

  1. The maximum element in the submatrix is at most k.
  2. In the submatrix, every row (when read from left to right) is sorted in non‑increasing order.

A submatrix is defined by four indices (x1, y1, x2, y2) such that the submatrix contains grid[x][y] for all x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2.

For example, given grid = [[4,3,2,1],[8,7,6,1]] and k = 3, the answer is 8.

Key Insights

  • The “maximum element ≤ k” condition is equivalent to requiring every element in the submatrix is ≤ k.
  • The “each row sorted in non‑increasing order” condition means that for any chosen contiguous subarray from a row, the natural order in that row must not “violate” non‑increasing order.
  • For each row, it is useful to precompute:
    • A “non‑increasing” left index array: for each column j, the earliest column index L such that the subarray from L to j is non‑increasing.
    • A “validity” segment with respect to k: while scanning a row, if an element is > k then no subarray including that element can be used.
  • Once the per‑row “effective left index” is computed (as the maximum of the two constraints – non‑increasing and ≤k), a subarray of a row (columns [c1, c2]) is valid if and only if effectiveLeft[i][c2] ≤ c1.
  • The final answer is obtained by iterating over every possible contiguous column interval [c1, c2] and “merging” rows. For fixed column indices, one can count contiguous groups of rows such that for every row in that block, the corresponding effective left index (at column c2) does not force the starting column to be greater than c1.
  • Then for each column pair, if a block of L consecutive rows are valid, there are L*(L+1)/2 submatrices from that vertical block with these fixed columns.

Space and Time Complexity

Time Complexity: O(m * n^2) in the worst-case because we iterate over all pairs of columns (O(n^2)) and for each such pair scan all m rows. Space Complexity: O(m * n) for storing the precomputed effective left indices.

Solution

We can solve the problem in two main phases:

  1. Preprocessing per row:

    • For each row, compute an array named “left” where left[j] is the smallest index such that the subarray from left[j] to j is non‑increasing. This is done in one pass per row.
    • Also, while scanning the row, maintain a pointer (say lastInvalid) which resets whenever we encounter an element > k. Thus, for column j, if grid[i][j] ≤ k the subarray is only valid if we start from an index ≥ lastInvalid.
    • Combine these two constraints by defining an “effective left” value: effectiveLeft[i][j] = max(left[j], lastInvalid). If grid[i][j] > k then mark effectiveLeft[i][j] as “invalid” (for example, set to a value larger than any valid column index).

  2. Count submatrices:

    • For every possible column interval [c1, c2] (with c1 ≤ c2), scan over rows.
    • For each row i, the subarray (row i, columns [c1, c2]) is valid if effectiveLeft[i][c2] ≤ c1.
    • Count consecutive rows that are valid. For a contiguous block of L valid rows, these rows yield L*(L+1)/2 submatrices (by choosing any contiguous subset of these rows).
    • Sum over all column intervals.

This approach “reduces” the two-dimensional submatrix counting to two nested loops over columns and one loop over rows.

A few key points and potential pitfalls:

  • Make sure to correctly update the “non‑increasing” left boundary because it “spills over” the entire row.
  • Reset the lastInvalid pointer when an element > k is encountered.
  • When scanning rows for a fixed column interval, use a running count of consecutive valid rows and add it to the answer when an invalid row is hit (or at the end of the row).

Code Solutions

Below are code solutions in four languages with detailed line‐by‐line comments.

# Python solution

def count_submatrices(grid, k):
    m, n = len(grid), len(grid[0])
    # effectiveLeft[i][j] will store the smallest column index from which
    # the subarray ending at j in row i is both non-increasing and has all elements <= k.
    effectiveLeft = [[n]*n for _ in range(m)]
    
    for i in range(m):
        # left boundary for non-increasing condition in the row
        left = [0] * n  
        left[0] = 0
        # lastInvalid: next index after a cell > k (i.e. cannot be included)
        lastInvalid = 0
        if grid[i][0] > k:
            lastInvalid = 1
            left[0] = 0  # left remains 0 but effective value will become > valid range.
        for j in range(1, n):
            # update left array for non-increasing property:
            if grid[i][j-1] >= grid[i][j]:
                left[j] = left[j-1]
            else:
                left[j] = j
            # update lastInvalid depending on k condition:
            if grid[i][j] > k:
                lastInvalid = j+1
            # effective left is the max of left[j] and lastInvalid.
            effectiveLeft[i][j] = max(left[j], lastInvalid)
    
    ans = 0
    # Iterate over every possible column pair [c1, c2]
    for c1 in range(n):
        for c2 in range(c1, n):
            validRows = 0  # count consecutive valid rows
            for i in range(m):
                # A row is valid for columns [c1,c2] if effectiveLeft[i][c2] <= c1.
                if effectiveLeft[i][c2] <= c1:
                    validRows += 1
                else:
                    # If row i is invalid, add submatrices from previous consecutive block.
                    ans += validRows * (validRows + 1) // 2
                    validRows = 0
            # After iterating over rows, add contribution from remaining block (if any).
            ans += validRows * (validRows + 1) // 2
    return ans

# Example usage:
grid = [[4,3,2,1],
        [8,7,6,1]]
k = 3
print(count_submatrices(grid, k))  # Expected output: 8
← Back to All Questions