CountSubmatrices.java

package dp.problems;

import utils.Reader;
import java.io.IOException;

// Leetcode Problem: https://leetcode.com/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/description/ 
class CountSubMatrices {
    public static void main (String[] args) throws IOException {
        Reader reader = new Reader();

        int n = reader.nextInt();
        int m = reader.nextInt();
        int k = reader.nextInt();

        int[][] grid = new int[n][m];

        for(int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                grid[i][j] = reader.nextInt();
            }
        }
    
        System.out.println(countSubmatrices(grid, k));
    }

    public static int countSubmatrices(int[][] grid, int k) {
        int n = grid.length;
        int m = grid[0].length;

        int[][] dp = new int[n][m];
        int count = 0;

        for (int i=0; i<n; i++) {
            int rowSum = 0;
            for (int j=0; j<m; j++) {
                rowSum += grid[i][j];
                dp[i][j] = (i > 0) ? (dp[i-1][j] + rowSum) : rowSum;

                if (dp[i][j] <= k) {
                    count++;
                }
            }
        }

        return count;
    }
}