Recuento de subarrays cuadradas con promedio de al menos K

Dada una array arr[][] de tamaño NxM y un número entero K , la tarea es encontrar el recuento de subarrays cuadradas en la array dada con el promedio de elementos mayor o igual que K .

Ejemplos:

Entrada: K = 4, arr[][] = {{2, 2, 3}, {3, 4, 5}, {4, 5, 5}}
Salida: 7
Explicación: 
Las siguientes subarrays cuadradas tienen un promedio mayor que o igual a K:

  1. Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(2, 2)}. El promedio de la subarray es igual a 4.
  2. Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(2, 3)}. El promedio de la subarray es igual a 5.
  3. Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(3, 1)}. El promedio de la subarray es igual a 4.
  4. Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(3, 2)}. El promedio de la subarray es igual a 5.
  5. Subarrays cuadradas de dimensión (1×1), formadas tomando los elementos en las posiciones {(3, 3)}. El promedio de la subarray es igual a 5.
  6. Subarrays cuadradas de dimensión (2×2), formadas tomando los elementos en las posiciones {(2, 1), (2, 2), (3, 1), (3, 2)}. El promedio de la subarray es igual a (3+4+4+5 = 16)/4 = 4.
  7. Subarrays cuadradas de dimensión (2×2), formadas tomando los elementos en las posiciones {(2, 2), (2, 3), (3, 2), (3, 3)}. El promedio de la subarray es igual a (4+5+5+5 = 19)/4 = 4,75.

Por lo tanto, hay totales de 7 subarrays cuadradas con un promedio mayor o igual a K.

Entrada: K = 3, arr[][] = {{1, 1, 1}, {1, 1, 1}}
Salida: 0

Enfoque ingenuo: el enfoque más simple es generar todas las subarrays cuadradas posibles y verificar que la suma de todos los elementos del subcuadrado sea mayor o igual a K multiplicado por el tamaño de la subarray.

Complejidad de Tiempo: O(N 3 * M 3
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la array de suma de prefijos que da como resultado un cálculo de tiempo constante de la suma de una subarray. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos contar como 0 para almacenar el recuento de subarrays con un promedio mayor o igual a K .
  • Calcule la suma del prefijo de la array arr[][] y guárdela en un vector de vectores , digamos pre[][] .
  • Recorra cada elemento de la array usando las variables i y j y realice los siguientes pasos:
    • Inicialice dos variables, digamos l como i y r como j .
    • Iterar hasta que l y r sean mayores que 0 y en cada iteración realizar los siguientes pasos:
      • Calcule la suma de la subarray cuadrada con el vértice inferior derecho como (i, j) y el vértice superior izquierdo como (l, r) y guárdelo en una variable, digamos sum , es decir sum = pre[i][j] – pre[l-1][r] – pre[l][r-1] + pre[l-1][r-1] .
        • Ahora, si el valor de K*(i-l+1)*(j-r+1) es igual a la suma , entonces incremente el conteo en 1 .
        • Disminuya l y r en 1 .
  • Finalmente, después de completar los pasos anteriores, imprima el valor de la cuenta como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 1000
 
// Function to count submatrixes with
// average greater than or equals to K
int cntMatrices(vector<vector<int> > arr, int N, int M,
                int K)
{
 
    // Stores count of submatrices
    int cnt = 0;
 
    // Stores the prefix sum of matrix
    vector<vector<int> > pre(N + 1, vector<int>(M + 1, 0));
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // Iterate over the range
        // [1, M]
        for (int j = 1; j <= M; j++) {
 
            // Update the prefix sum
            pre[i][j] = arr[i - 1][j - 1] + pre[i - 1][j]
                        + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // Iterate over the range
        // [1, M]
        for (int j = 1; j <= M; j++) {
 
            // Iterate until l and r
            // are greater than 0
            for (int l = i, r = j; l > 0 && r > 0;
                 l--, r--) {
 
                // Update count
                int sum1 = (K * (i - l + 1) * (i - r + 1));
 
                // Stores sum of submatrix
                // with bottom right corner
                // as (i, j) and top left
                // corner as (l, r)
                int sum2 = pre[i][j] - pre[l - 1][r]
                           - pre[l][r - 1]
                           + pre[l - 1][r - 1];
 
                // If sum1 is less than or
                // equal to sum2
                if (sum1 <= sum2)
 
                    // Increment cnt by 1
                    cnt++;
            }
        }
    }
 
    // Return cnt as the answer
    return cnt;
}
 
// Driver Code
int main()
{
    // Given Input
    vector<vector<int> > arr
        = { { 2, 2, 3 }, { 3, 4, 5 }, { 4, 5, 5 } };
    int K = 4;
    int N = arr.size();
    int M = arr[0].size();
 
    // Function Call
    cout << cntMatrices(arr, N, M, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static int MAX = 1000;
 
// Function to count submatrixes with
// average greater than or equals to K
static int cntMatrices(int[][] arr, int N,
                    int M, int K)
{
     
    // Stores count of submatrices
    int cnt = 0;
 
    // Stores the prefix sum of matrix
    int[][] pre = new int[N + 1][M + 1];
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // Iterate over the range
        // [1, M]
        for(int j = 1; j <= M; j++)
        {
             
            // Update the prefix sum
            pre[i][j] = arr[i - 1][j - 1] + pre[i - 1][j] +
                            pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // Iterate over the range
        // [1, M]
        for(int j = 1; j <= M; j++)
        {
             
            // Iterate until l and r
            // are greater than 0
            for(int l = i, r = j;
                    l > 0 && r > 0; l--, r--)
            {
                 
                // Update count
                int sum1 = (K * (i - l + 1) *
                                (i - r + 1));
 
                // Stores sum of submatrix
                // with bottom right corner
                // as (i, j) and top left
                // corner as (l, r)
                int sum2 = pre[i][j] - pre[l - 1][r] -
                       pre[l][r - 1] + pre[l - 1][r - 1];
 
                // If sum1 is less than or
                // equal to sum2
                if (sum1 <= sum2)
 
                    // Increment cnt by 1
                    cnt++;
            }
        }
    }
 
    // Return cnt as the answer
    return cnt;
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given Input
    int[][] arr = { { 2, 2, 3 },
                    { 3, 4, 5 },
                    { 4, 5, 5 } };
    int K = 4;
    int N = arr.length;
    int M = arr[0].length;
 
    // Function Call
    System.out.println( cntMatrices(arr, N, M, K));
}
}
 
// This code is contributed by avijitmondal1998

Python3

# Python3 program for the above approach
# define MAX 1000
 
# Function to count submatrixes with
# average greater than or equals to K
def cntMatrices(arr, N, M, K):
 
    # Stores count of submatrices
    cnt = 0
 
    # Stores the prefix sum of matrix
    pre = [[0 for i in range(M + 1)]
              for i in range(N + 1)]
               
    # Iterate over the range [1, N]
    for i in range(1, N + 1):
         
        # Iterate over the range
        # [1, M]
        for j in range(1, M + 1):
             
            # Update the prefix sum
            pre[i][j] = (arr[i - 1][j - 1] +
                         pre[i - 1][j] +
                         pre[i][j - 1] -
                         pre[i - 1][j - 1])
 
    # Iterate over the range [1, N]
    for i in range(1, N + 1):
         
        # Iterate over the range
        # [1, M]
        for j in range(1, M + 1):
             
            # Iterate until l and r
            # are greater than 0
            l, r = i, j
            while l > 0 and r > 0:
                 
                # Update count
                sum1 = (K * (i - l + 1) * (i - r + 1))
 
                # Stores sum of submatrix
                # with bottom right corner
                # as (i, j) and top left
                # corner as (l, r)
                sum2 = (pre[i][j] -
                        pre[l - 1][r] - pre[l][r - 1] +
                        pre[l - 1][r - 1])
 
                # If sum1 is less than or
                # equal to sum2
                if (sum1 <= sum2):
                     
                    # Increment cnt by 1
                    cnt += 1
                     
                l -= 1
                r -= 1
 
    # Return cnt as the answer
    return cnt
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    arr = [ [ 2, 2, 3 ],
            [ 3, 4, 5 ],
            [ 4, 5, 5 ] ]
    K = 4
    N = len(arr)
    M = len(arr[0])
 
    # Function Call
    print(cntMatrices(arr, N, M, K))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
class GFG
{
 
  static int MAX = 1000;
 
  // Function to count submatrixes with
  // average greater than or equals to K
  static int cntMatrices(int[,] arr, int N,
                         int M, int K)
  {
 
    // Stores count of submatrices
    int cnt = 0;
 
    // Stores the prefix sum of matrix
    int[,] pre = new int[N + 1, M + 1];
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
 
      // Iterate over the range
      // [1, M]
      for(int j = 1; j <= M; j++)
      {
 
        // Update the prefix sum
        pre[i, j] = arr[i - 1, j - 1] + pre[i - 1, j] +
          pre[i, j - 1] - pre[i - 1, j - 1];
      }
    }
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
 
      // Iterate over the range
      // [1, M]
      for(int j = 1; j <= M; j++)
      {
 
        // Iterate until l and r
        // are greater than 0
        for(int l = i, r = j;
            l > 0 && r > 0; l--, r--)
        {
 
          // Update count
          int sum1 = (K * (i - l + 1) *
                      (i - r + 1));
 
          // Stores sum of submatrix
          // with bottom right corner
          // as (i, j) and top left
          // corner as (l, r)
          int sum2 = pre[i, j] - pre[l - 1, r] -
            pre[l, r - 1] + pre[l - 1, r - 1];
 
          // If sum1 is less than or
          // equal to sum2
          if (sum1 <= sum2)
 
            // Increment cnt by 1
            cnt++;
        }
      }
    }
 
    // Return cnt as the answer
    return cnt;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
 
    // Given Input
    int[,] arr = { { 2, 2, 3 },
                  { 3, 4, 5 },
                  { 4, 5, 5 } };
    int K = 4;
    int N = arr.GetLength(0);
    int M = arr.GetLength(0);
 
    // Function Call
    Console.WriteLine( cntMatrices(arr, N, M, K));
  }
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
// Javascript program for the above approach
let MAX = 1000
 
// Function to count submatrixes with
// average greater than or equals to K
function cntMatrices(arr, N, M, K) {
 
    // Stores count of submatrices
    let cnt = 0;
 
    // Stores the prefix sum of matrix
 
    let pre = new Array(N + 1).fill(0).map(() => new Array(M + 1).fill(0))
 
    // Iterate over the range [1, N]
    for (let i = 1; i <= N; i++) {
 
        // Iterate over the range
        // [1, M]
        for (let j = 1; j <= M; j++) {
 
            // Update the prefix sum
            pre[i][j] = arr[i - 1][j - 1] + pre[i - 1][j]
                + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }
 
    // Iterate over the range [1, N]
    for (let i = 1; i <= N; i++) {
 
        // Iterate over the range
        // [1, M]
        for (let j = 1; j <= M; j++) {
 
            // Iterate until l and r
            // are greater than 0
            for (let l = i, r = j; l > 0 && r > 0;
                l--, r--) {
 
                // Update count
                let sum1 = (K * (i - l + 1) * (i - r + 1));
 
                // Stores sum of submatrix
                // with bottom right corner
                // as (i, j) and top left
                // corner as (l, r)
                let sum2 = pre[i][j] - pre[l - 1][r]
                    - pre[l][r - 1]
                    + pre[l - 1][r - 1];
 
                // If sum1 is less than or
                // equal to sum2
                if (sum1 <= sum2)
 
                    // Increment cnt by 1
                    cnt++;
            }
        }
    }
 
    // Return cnt as the answer
    return cnt;
}
 
// Driver Code
 
// Given Input
let arr = [[2, 2, 3], [3, 4, 5], [4, 5, 5]];
let K = 4;
let N = arr.length;
let M = arr[0].length;
 
// Function Call
document.write(cntMatrices(arr, N, M, K));
 
// This code is contributed by _saurabh_jaiswal.
</script>
Producción

7

Complejidad de tiempo: O(M * N * (min(N, M))
Espacio auxiliar: O(M * N)

Publicación traducida automáticamente

Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *