#leetcode #medium #barclays 3070. Count Submatrices with Top-Left Element and Sum Less Than k Дейлик литкода 18.03.2026 You are given a 0-indexed integer matrix grid and an integer k. Return the number of submatrices that contain the top-left element of the grid, and have a sum less than or equal to k. Мы начинаем с верхнего левого угла и обходим матрицу в порядке строк, рассматривая каждую позицию (i,j)в качестве нижнего правого угла подматрицы. Для эффективного вычисления сумм подматриц за один проход мы поддерживаем массив cols[j], который хранит сумму элементов в столбце j до текущей строки. При обработке строки i мы перебираем столбцы j слева направо. Для каждого столбца мы добавляем grid[i][j] к cols[j], а затем накапливаем cols[j] в текущую сумму для текущей строки. Если накопленная сумма ≤k, мы увеличиваем результат на 1. class Solution { public int countSubmatrices(int[][] grid, int k) { int n = grid.length, m = grid[0].length; int[] cols = new int[m]; int count = 0; for (int i = 0; i < n; i++) { int row = 0; for (int j = 0; j < m; j++) { cols[j] += grid[i][j]; row += cols[j]; if (row <= k) { count++; } } } return count; } } func countSubmatrices(grid [][]int, k int) int { if len(grid) == 0 || len(grid[0]) == 0 { return 0 } n := len(grid) m := len(grid[0]) cols := make([]int, m) count := 0 for i := 0; i < n; i++ { row := 0 for j := 0; j < m; j++ { cols[j] += grid[i][j] row += cols[j] if row <= k { count++ } } } return count } class Solution { fun countSubmatrices(grid: Array<IntArray>, k: Int): Int { if (grid.isEmpty() || grid[0].isEmpty()) return 0 val n = grid.size val m = grid[0].size val cols = IntArray(m) var count = 0 for (i in 0 until n) { var rowSum = 0 for (j in 0 until m) { cols[j] += grid[i][j] rowSum += cols[j] if (rowSum <= k) { count++ } } } return count } }