Skip to main content
Talentd

Find Sorted Submatrices With Maximum Element at Most K - Solution & Explanation

HardPremiumFree on FleetCodeArrayStackMatrixMonotonic Stack3 min read
Practice this problem

Problem Statement

You are given a 2D matrix grid of size m x n. You are also given a non-negative integer k.

Return the number of submatrices of grid that satisfy the following conditions:

  • The maximum element in the submatrix less than or equal to k.
  • Each row in the submatrix is sorted in non-increasing order.

A submatrix (x1, y1, x2, y2) is a matrix that forms by choosing all cells grid[x][y] where x1 <= x <= x2 and y1 <= y <= y2.

 

Example 1:

Input: grid = [[4,3,2,1],[8,7,6,1]], k = 3

Output: 8

Explanation:

The 8 submatrices are:

  • [[1]]
  • [[1]]
  • [[2,1]]
  • [[3,2,1]]
  • [[1],[1]]
  • [[2]]
  • [[3]]
  • [[3,2]]

Example 2:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], k = 1

Output: 36

Explanation:

There are 36 submatrices of grid. All submatrices have their maximum element equal to 1.

Example 3:

Input: grid = [[1]], k = 1

Output: 1

 

Constraints:

  • 1 <= m == grid.length <= 103
  • 1 <= n == grid[i].length <= 103
  • 1 <= grid[i][j] <= 109
  • 1 <= k <= 109

 

​​​​​​

Approach Overview

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Submatrix EnumerationO(m^2 * n^2)O(1)Conceptual baseline or when matrix size is very small
Row Preprocessing + Monotonic StackO(m * n)O(n)General optimal solution for large matrices

Video Solution

Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,616 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Sorted Submatrices With Maximum Element at Most K easy or hard?
The problem is classified as Hard because it combines multiple concepts: matrix preprocessing, sorted constraints, and monotonic stack rectangle counting. Recognizing the transformation to a histogram-style problem is the main difficulty.
Find Sorted Submatrices With Maximum Element at Most K Python/Java solution
Implement the algorithm by first computing a width matrix that stores the longest sorted segment ending at each column with values ≤ k. Then iterate row by row while maintaining a monotonic stack to count rectangles. The same logic translates directly across Python, Java, C++, and Go implementations.
How to solve Find Sorted Submatrices With Maximum Element at Most K in O(n)?
For an m × n matrix the optimal complexity becomes O(m * n). Compute the width of the longest sorted segment ending at each cell while ensuring the value ≤ k. Then iterate column-wise and use a monotonic stack to maintain increasing widths, allowing efficient counting of all valid submatrices ending at each row.
What is the best approach for Find Sorted Submatrices With Maximum Element at Most K?
The optimal approach uses row preprocessing combined with a monotonic stack. First compute the maximum valid sorted width ending at every cell where values are ≤ k. Then treat each column as a histogram and use a monotonic stack to count submatrices while maintaining the minimum width constraint. This runs in O(m * n) time with O(n) extra space.
Is Find Sorted Submatrices With Maximum Element at Most K asked at Google/Amazon/Meta?
Matrix counting problems combined with monotonic stack patterns appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of histogram rectangle counting and submatrix enumeration are common in hard-level coding interviews.
What data structure is used in Find Sorted Submatrices With Maximum Element at Most K?
The key data structure is a monotonic stack. It maintains rows with increasing width values while processing each column. This allows efficient aggregation of submatrix counts while preserving the minimum width constraint required for a valid sorted submatrix.
What is the time complexity of Find Sorted Submatrices With Maximum Element at Most K?
The optimal algorithm runs in O(m * n) time, where m is the number of rows and n is the number of columns. Each cell is processed once during preprocessing and once during the monotonic stack pass. The auxiliary space complexity is O(n) for the stack and running counts.

Ready to solve this problem?

Practice Find Sorted Submatrices With Maximum Element at Most K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximal Rectangle