Find Sorted Submatrices With Maximum Element at Most K

Find Sorted Submatrices With Maximum Element at Most K - Problem

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 is less than or equal to k
Each row in the submatrix is sorted in non-increasing order

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

Input & Output

Example 1 — Basic Case

$ Input: grid = [[7,6,3],[2,1,0]], k = 2

› Output: 4

💡 Note: Valid submatrices: (0,2,0,2) contains [3], (1,0,1,2) contains [2,1,0], (1,1,1,1) contains [1], (1,1,1,2) contains [1,0]. All have max ≤ 2 and non-increasing rows.

Example 2 — Single Cell

$ Input: grid = [[1,2,3],[4,5,6]], k = 2

› Output: 2

💡 Note: Only single cells with value ≤ 2 are valid: grid[0][0]=1 and grid[1][0]=1. Multi-cell submatrices fail row sorting or max constraint.

Example 3 — All Valid

$ Input: grid = [[2,1],[1,0]], k = 5

› Output: 6

💡 Note: All elements ≤ 5 and all rows non-increasing. Valid submatrices: 4 single cells + 2 row submatrices + entire 2×2 matrix = 6 total.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 100
0 ≤ grid[i][j] ≤ 100
0 ≤ k ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D grid with elements and threshold k

Check Constraints

Validate max ≤ k and rows non-increasing

Count Valid

Return number of qualifying submatrices

Key Takeaway

🎯 Key Insight: Use monotonic stack to efficiently count rectangles for each column range, avoiding redundant submatrix validation

Asked in

G Google 15 f Meta 8 a Amazon 12

The key insight is to use monotonic stack to efficiently count rectangles for each column range. The optimal approach fixes column boundaries and uses height arrays with stack-based rectangle counting. Time: O(mn²), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack Optimization	O(m*n²)	O(m)	Use monotonic stack to efficiently count valid submatrices for each column range
Brute Force	O(m²n³)	O(1)	Check all possible submatrices and validate conditions

Monotonic Stack Optimization — Algorithm Steps

For each column range (left, right)
Calculate height array: how many consecutive valid rows ending at each position
Use monotonic stack to count rectangles with these heights
Sum all valid rectangle counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Column Range

Fix left and right column boundaries

Build Heights

Calculate valid consecutive rows for each position

Stack Processing

Use monotonic stack to count rectangles efficiently

Sum Results

Add rectangle counts for all column ranges

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* data;
    int top;
    int capacity;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (int*)malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

void push(Stack* stack, int item) {
    stack->data[++stack->top] = item;
}

int pop(Stack* stack) {
    return stack->data[stack->top--];
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

int peek(Stack* stack) {
    return stack->data[stack->top];
}

long long countRectangles(int* heights, int size) {
    Stack* stack = createStack(size + 1);
    long long count = 0;
    
    for (int i = 0; i <= size; i++) {
        int h = i < size ? heights[i] : 0;
        
        while (!isEmpty(stack) && heights[peek(stack)] > h) {
            int height = heights[pop(stack)];
            int width = isEmpty(stack) ? i : i - peek(stack) - 1;
            count += (long long)height * width * (width + 1) / 2;
        }
        push(stack, i);
    }
    
    free(stack->data);
    free(stack);
    return count;
}

int solution(int** grid, int gridSize, int* gridColSize, int k) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    long long count = 0;
    
    // For each column range
    for (int left = 0; left < n; left++) {
        int* heights = (int*)calloc(m, sizeof(int));
        
        for (int right = left; right < n; right++) {
            // Update heights for current column range
            for (int i = 0; i < m; i++) {
                if (grid[i][right] <= k) {
                    // Check if row segment [left:right+1] is non-increasing
                    int valid = 1;
                    for (int j = left; j < right; j++) {
                        if (grid[i][j] < grid[i][j + 1]) {
                            valid = 0;
                            break;
                        }
                    }
                    
                    if (valid) {
                        heights[i]++;
                    } else {
                        heights[i] = 0;
                    }
                } else {
                    heights[i] = 0;
                }
            }
            
            // Count rectangles using monotonic stack
            count += countRectangles(heights, m);
        }
        
        free(heights);
    }
    
    return (int)count;
}

int main() {
    // Simplified input parsing for demonstration
    int grid_data[][3] = {{7,6,3},{2,1,0}};
    int* grid[2];
    int gridColSize[2] = {3, 3};
    
    for (int i = 0; i < 2; i++) {
        grid[i] = grid_data[i];
    }
    
    int k = 2;
    
    int result = solution(grid, 2, gridColSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m*n²)

O(n²) column pairs × O(m) monotonic stack operations per pair

⚠ Quadratic Growth

Space Complexity

O(m)

Stack and height array of size m for each column range

✓ Linear Space

18.5K Views

Medium Frequency

~35 min Avg. Time

432 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler