Find Sorted Submatrices With Maximum Element at Most K - Video Solutions

Problem Overview: Given a matrix and an integer k, count submatrices that satisfy two constraints: every row inside the submatrix remains non‑decreasing (sorted left to right) and the maximum element inside the submatrix is at most k.

Approach 1: Brute Force Submatrix Enumeration (O(m^2 * n^2), O(1) space)

Enumerate every possible submatrix using four boundaries. For each candidate, scan all cells to verify two conditions: values do not exceed k and every row remains non‑decreasing across the selected columns. This approach directly checks the definition but repeats large amounts of work because each submatrix is validated from scratch. It works for very small matrices but quickly becomes infeasible as matrix size grows.

Approach 2: Row Preprocessing + Monotonic Stack (O(m * n), O(n) space)

Preprocess each cell to compute the maximum width of a valid sorted segment ending at that column. While scanning a row, extend the width if matrix[i][j] >= matrix[i][j-1] and matrix[i][j] ≤ k; otherwise reset the width to 0. This converts the matrix into a grid where each cell represents the largest valid horizontal span of a sorted segment ending there.

Now treat each column as a histogram where the value is the width computed above. For each row while moving downward, use a monotonic stack to maintain increasing widths. The stack helps determine how many submatrices can end at the current row by aggregating contributions of previous rows while maintaining the minimum width constraint. This technique is similar to counting rectangles in histogram problems and avoids recomputing ranges repeatedly.

The key insight: for a submatrix to remain sorted, the limiting factor is the minimum valid width among its rows. The monotonic stack efficiently tracks these minima while extending submatrices vertically. Combined with matrix preprocessing from matrix traversal and standard array operations, the algorithm counts all valid rectangles in linear time.

Recommended for interviews: The monotonic stack solution. Interviewers expect you to recognize the transformation from matrix constraints to a histogram-style counting problem. Mentioning the brute force method first shows you understand the constraints, but implementing the O(m * n) stack approach demonstrates strong algorithmic problem solving.