Find Sorted Submatrices With Maximum Element at Most K

Explore More Solutions

• Java Solution
• Python Solution

Problem Description

Welcome to the world of submatrices, where the only thing more confusing than your last relationship is figuring out how many sorted submatrices you can find with a maximum element at most K! Imagine you’re at a buffet, and you can only take food items that are less than or equal to your calorie limit (K). But instead of food, we have numbers in a grid, and instead of calories, we have the maximum element constraint.

In this problem, you are given a 2D grid of integers, and your task is to count all the submatrices where the maximum element is less than or equal to K. Sounds simple, right? Well, it’s like trying to find a needle in a haystack, except the haystack is a grid, and the needle is a sorted submatrix.

Code Solution

Copy Code

struct T {
  int subarrayWidth;
  int rowIndex;
  int accumulatedSubmatrices;
};

class Solution {
 public:
  long long countSubmatrices(vector>& grid, int k) {
    int m = grid.size();
    int n = grid[0].size();
    long ans = 0;
    vector> dp(m, vector(n));
    vector> stacks(n);

    for (int j = 0; j < n; ++j)
      stacks[j].emplace(0, -1, 0);

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] > k) {
          stacks[j] = stack();
          stacks[j].emplace(0, i, 0);
        } else {
          dp[i][j] = 1;
          if (j > 0 && grid[i][j - 1] <= k && grid[i][j - 1] >= grid[i][j])
            dp[i][j] += dp[i][j - 1];
          const int width = dp[i][j];
          stack& stack = stacks[j];
          while (!stack.empty() && width < stack.top().subarrayWidth)
            stack.pop();
          const int height = i - stack.top().rowIndex;
          const int newSubmatrices = width * height;
          const int accumulatedSubmatrices =
              stack.top().accumulatedSubmatrices + newSubmatrices;
          ans += accumulatedSubmatrices;
          stack.emplace(width, i, accumulatedSubmatrices);
        }

    return ans;
  }
};

Approach Explanation

The code uses a dynamic programming approach combined with a stack to efficiently count the valid submatrices. The dp array keeps track of the number of valid subarrays ending at each position in the grid. The stack helps manage the widths and heights of these subarrays, allowing us to calculate the number of accumulated submatrices quickly.

1. Initialization: We initialize a stack for each column to keep track of valid subarray widths and their corresponding row indices.
2. Iterate through the grid: For each element, we check if it exceeds K. If it does, we reset the stack for that column.
3. Count valid subarrays: If the current element is valid, we update the dp array and use the stack to calculate the number of valid submatrices that can be formed.

Time and Space Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. We traverse each element of the grid once.

Space Complexity: O(n), as we maintain a stack for each column.

Real-World Example

Imagine you are at a party with a buffet table filled with various dishes. Each dish has a calorie count, and you can only eat dishes that have a calorie count less than or equal to your limit (K). You want to find out how many combinations of dishes (submatrices) you can enjoy without exceeding your calorie limit. This problem is akin to finding those combinations in a grid of numbers, where each number represents the calorie count of a dish.

Similar Problems

• Count Subarrays With Maximum Element at Most K Solution in C++