Количество квадратных подматриц со средним значением не менее K

Учитывая матрицу arr[][] размера NxM и целое число K , задача состоит в том, чтобы найти количество квадратных подматриц в данной матрице со средним значением элементов, большим или равным K .

Примеры:

Input: K = 4, arr[][] = {{2, 2, 3}, {3, 4, 5}, {4, 5, 5}}
Output: 7
Explanation: 
The following square submatrices have an average greater than or equal to K:

1. Square submatrices of dimension (1×1), formed by taking the elements at positions {(2, 2)}. The average of the submatrix is equal to 4.
2. Square submatrices of dimension (1×1), formed by taking the elements at positions {(2, 3)}. The average of the submatrix is equal to 5.
3. Square submatrices of dimension (1×1), formed by taking the elements at positions {(3, 1)}. The average of the submatrix is equal to 4.
4. Square submatrices of dimension (1×1), formed by taking the elements at positions {(3, 2)}. The average of the submatrix is equal to 5.
5. Square submatrices of dimension (1×1), formed by taking the elements at positions {(3, 3)}. The average of the submatrix is equal to 5.
6. Square submatrices of dimension (2×2), formed by taking the elements at positions {(2, 1), (2, 2), (3, 1), (3, 2)}. The average of the submatrix is equal to (3+4+4+5 = 16)/4 = 4.
7. Square submatrices of dimension (2×2), formed by taking the elements at positions {(2, 2), (2, 3), (3, 2), (3, 3)}. The average of the submatrix is equal to (4+5+5+5 = 19)/4 = 4.75.

Therefore, there are totals of 7 square submatrices with an average greater than or equals to K.

Input: K = 3, arr[][] = {{1, 1, 1}, {1, 1, 1}}
Output: 0

Наивный подход: самый простой подход состоит в том, чтобы сгенерировать все возможные квадратные подматрицы и проверить, что сумма всех элементов подквадрата больше или равна K , умноженному на размер подматрицы.

Временная сложность: O(N ³ * M ³ )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать, используя матрицу суммы префиксов, что приводит к вычислению суммы подматрицы за постоянное время. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, count как 0 , чтобы сохранить количество подматриц со средним значением, большим или равным K .
• Вычислите сумму префиксов матрицы arr[][] и сохраните ее в векторе векторов, скажем, pre[][] .
• Пройдитесь по каждому элементу матрицы, используя переменные i и j , и выполните следующие шаги:
  • Инициализируйте две переменные, скажем, l как i и r как j .
  • Повторяйте до тех пор, пока l и r не станут больше 0 , и на каждой итерации выполните следующие шаги:
    • Вычислите сумму квадратной подматрицы с нижней правой вершиной как (i, j) и верхней левой вершиной как (l, r) и сохраните ее в переменной, скажем, sum , т.е. sum = pre[i][j] – пре[l-1][r] – пре[l][r-1] + пре[l-1][r-1] .
      • Теперь, если значение K*(i-l+1)*(j-r+1) равно sum , тогда увеличьте счетчик на 1 .
      • Уменьшите l и r на 1 .
• Наконец, после выполнения вышеуказанных шагов выведите значение счетчика в качестве результата.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M * N * (мин(N, M))
Вспомогательное пространство: O(M * N)