Longitud del subarreglo común más grande en todas las filas de Matrix dada

Dada una array mat[][] de tamaño N×M donde cada fila de la array es una permutación de los elementos de [1, M] , la tarea es encontrar la longitud máxima del subarreglo presente en cada fila de la array .

Ejemplos:

Entrada: mat[][] = {{1, 2, 3, 4, 5}, {2, 3, 4, 1, 5}, {5, 2, 3, 4, 1}, {1, 5, 2, 3, 4}}
Salida: 3
Explicación: 
En cada fila, {2, 3, 4} es el subarreglo común más largo presente en todas las filas de la array.

Entrada: mat[][] = {{4, 5, 1, 2, 3, 6, 7}, {1, 2, 4, 5, 7, 6, 3}, {2, 7, 3, 4, 5, 1, 6}}
Salida: 2

Enfoque ingenuo: la forma más sencilla de resolver el problema es generar todo el subarreglo posible de la primera fila de la array y luego verificar si las filas restantes contienen ese subarreglo o no.

Complejidad temporal: O(M×N ² )
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar creando una array , digamos dp[][] que almacena la posición del elemento en cada fila y luego verifica si el índice de elementos actual y anterior en cada fila tiene una diferencia de 1 o no . Siga los pasos a continuación para resolver el problema:

• Inicialice una array, digamos dp[][] que almacena la posición de cada elemento en cada fila.
• Para llenar la array dp[][] , Iterar en el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
  • Iterar en el rango [0, M-1] usando la variable j y modificar el valor de dp[i][arr[i][j]] como j .
• Inicialice la variable, digamos ans que almacena la longitud del subarreglo común más largo en todas las filas y len que almacena la longitud del subarreglo común en todas las filas.
• Iterar en el rango [1, M-1] usando la variable i y realizar los siguientes pasos:
  • Inicialice una verificación de variable booleana como 1 , que verifica si a[i][0] viene después de a[i-1][0] en cada fila o no.
  • Iterar en el rango [1, N-1] usando la variable j y realizar los siguientes pasos:
    • Si dp[j][arr[0][i-1]] + 1 != dp[j][arr[0][i]] , modifique el valor de check como 0 y finalice el ciclo.
  • Si el valor de la verificación es 1 , aumente el valor de len en 1 y modifique el valor de ans como max(ans, len) .
  • Si el valor de la verificación es 0 , modifique el valor de len como 1 .
• Después de completar los pasos anteriores, imprima el valor de ans como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find longest common subarray
// in all the rows of the matrix
int largestCommonSubarray(
    vector<vector<int> > arr,
    int n, int m)
{
    // Array to store the position
    // of element in every row
    int dp[n][m + 1];
 
    // Traverse the matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // Store the position of
            // every element in every row
            dp[i][arr[i][j]] = j;
        }
    }
 
    // Variable to store length of largest
    // common Subarray
    int ans = 1;
    int len = 1;
 
    // Traverse through the matrix column
    for (int i = 1; i < m; i++) {
        // Variable to check if every row has
        // arr[i][j] next to arr[i-1][j] or not
        bool check = true;
 
        // Traverse through the matrix rows
        for (int j = 1; j < n; j++) {
            // Check if arr[i][j] is next to
            // arr[i][j-1] in every row or not
            if (dp[j][arr[0][i - 1]] + 1
                != dp[j][arr[0][i]]) {
                check = false;
                break;
            }
        }
 
        // If every row has arr[0][j] next
        // to arr[0][j-1] increment len by 1
        // and update the value of ans
        if (check) {
            len++;
            ans = max(ans, len);
        }
        else {
            len = 1;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
 
    // Given Input
    int n = 4;
    int m = 5;
    vector<vector<int> > arr{ { 4, 5, 1, 2, 3, 6, 7 },
                              { 1, 2, 4, 5, 7, 6, 3 },
                              { 2, 7, 3, 4, 5, 1, 6 } };
 
    int N = arr.size();
    int M = arr[0].size();
 
    // Function Call
    cout << largestCommonSubarray(arr, N, M);
 
    return 0;
}

// Java program for the above approach
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to find longest common subarray
// in all the rows of the matrix
static int largestCommonSubarray(int[][] arr,
                                 int n, int m)
{
     
    // Array to store the position
    // of element in every row
    int dp[][] = new int[n][m + 1];
 
    // Traverse the matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
             
            // Store the position of
            // every element in every row
            dp[i][arr[i][j]] = j;
        }
    }
 
    // Variable to store length of largest
    // common Subarray
    int ans = 1;
    int len = 1;
 
    // Traverse through the matrix column
    for(int i = 1; i < m; i++)
    {
         
        // Variable to check if every row has
        // arr[i][j] next to arr[i-1][j] or not
        boolean check = true;
 
        // Traverse through the matrix rows
        for(int j = 1; j < n; j++)
        {
             
            // Check if arr[i][j] is next to
            // arr[i][j-1] in every row or not
            if (dp[j][arr[0][i - 1]] + 1 !=
                dp[j][arr[0][i]])
            {
                check = false;
                break;
            }
        }
 
        // If every row has arr[0][j] next
        // to arr[0][j-1] increment len by 1
        // and update the value of ans
        if (check)
        {
            len++;
            ans = Math.max(ans, len);
        }
        else
        {
            len = 1;
        }
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Input
    int n = 4;
    int m = 5;
    int[][] arr = { { 4, 5, 1, 2, 3, 6, 7 },
                    { 1, 2, 4, 5, 7, 6, 3 },
                    { 2, 7, 3, 4, 5, 1, 6 } };
 
    int N = arr.length;
    int M = arr[0].length;
 
    // Function Call
    System.out.println(largestCommonSubarray(arr, N, M));
}
}
 
// This code is contributed by avijitmondal1998

# Python3 program for the above approach
 
# Function to find longest common subarray
# in all the rows of the matrix
def largestCommonSubarray(arr, n, m):
   
    # Array to store the position
    # of element in every row
    dp = [[0 for i in range(m+1)] for j in range(n)]
 
    # Traverse the matrix
    for i in range(n):
        for j in range(m):
           
            # Store the position of
            # every element in every row
            dp[i][arr[i][j]] = j
 
    # Variable to store length of largest
    # common Subarray
    ans = 1
    len1 = 1
 
    # Traverse through the matrix column
    for i in range(1,m,1):
        # Variable to check if every row has
        # arr[i][j] next to arr[i-1][j] or not
        check = True
 
        # Traverse through the matrix rows
        for j in range(1,n,1):
            # Check if arr[i][j] is next to
            # arr[i][j-1] in every row or not
            if (dp[j][arr[0][i - 1]] + 1 != dp[j][arr[0][i]]):
                check = False
                break
             
        # If every row has arr[0][j] next
        # to arr[0][j-1] increment len by 1
        # and update the value of ans
        if (check):
            len1 += 1
            ans = max(ans, len1)
 
        else:
            len1 = 1
 
    return ans
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    n = 4
    m = 5
    arr = [[4, 5, 1, 2, 3, 6, 7],
           [1, 2, 4, 5, 7, 6, 3],
           [2, 7, 3, 4, 5, 1, 6]]
 
    N = len(arr)
    M = len(arr[0])
 
    # Function Call
    print(largestCommonSubarray(arr, N, M))
     
    # This code is contributed by bgangwar59.

<script>
      // JavaScript program for the above approach
 
      // Function to find longest common subarray
      // in all the rows of the matrix
      function largestCommonSubarray(arr, n, m) {
          // Array to store the position
          // of element in every row
          let dp = Array(n).fill().map(() => Array(m + 1));
 
          // Traverse the matrix
          for (let i = 0; i < n; i++) {
              for (let j = 0; j < m; j++) {
                  // Store the position of
                  // every element in every row
                  dp[i][arr[i][j]] = j;
              }
          }
 
          // Variable to store length of largest
          // common Subarray
          let ans = 1;
          let len = 1;
 
          // Traverse through the matrix column
          for (let i = 1; i < m; i++) {
              // Variable to check if every row has
              // arr[i][j] next to arr[i-1][j] or not
              let check = true;
 
              // Traverse through the matrix rows
              for (let j = 1; j < n; j++) {
                  // Check if arr[i][j] is next to
                  // arr[i][j-1] in every row or not
                  if (dp[j][arr[0][i - 1]] + 1
                      != dp[j][arr[0][i]]) {
                      check = false;
                      break;
                  }
              }
 
              // If every row has arr[0][j] next
              // to arr[0][j-1] increment len by 1
              // and update the value of ans
              if (check) {
                  len++;
                  ans = Math.max(ans, len);
              }
              else {
                  len = 1;
              }
          }
          return ans;
      }
 
      // Driver Code
 
 
      // Given Input
      let n = 4;
      let m = 5;
      let arr = [[4, 5, 1, 2, 3, 6, 7],
      [1, 2, 4, 5, 7, 6, 3],
      [2, 7, 3, 4, 5, 1, 6]];
 
      let N = arr.length;
      let M = arr[0].length;
 
      // Function Call
      document.write(largestCommonSubarray(arr, N, M));
 
  // This code is contributed by Potta Lokesh
 
  </script>

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find longest common subarray
// in all the rows of the matrix
static int largestCommonSubarray(int [,]arr,
                                 int n, int m)
{
     
    // Array to store the position
    // of element in every row
    int [,]dp = new int[n,m + 1];
 
    // Traverse the matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
             
            // Store the position of
            // every element in every row
            dp[i,arr[i,j]] = j;
        }
    }
 
    // Variable to store length of largest
    // common Subarray
    int ans = 1;
    int len = 1;
 
    // Traverse through the matrix column
    for(int i = 1; i < m; i++)
    {
         
        // Variable to check if every row has
        // arr[i][j] next to arr[i-1][j] or not
        bool check = true;
 
        // Traverse through the matrix rows
        for(int j = 1; j < n; j++)
        {
             
            // Check if arr[i][j] is next to
            // arr[i][j-1] in every row or not
            if (dp[j,arr[0,i - 1]] + 1 !=
                dp[j,arr[0,i]])
            {
                check = false;
                break;
            }
        }
 
        // If every row has arr[0][j] next
        // to arr[0][j-1] increment len by 1
        // and update the value of ans
        if (check == true)
        {
            len++;
            ans = Math.Max(ans, len);
        }
        else
        {
            len = 1;
        }
    }
    return ans;
}
 
// Driver code
public static void Main()
{
     
    // Given Input
    int [,]arr = { { 4, 5, 1, 2, 3, 6, 7 },
                    { 1, 2, 4, 5, 7, 6, 3 },
                    { 2, 7, 3, 4, 5, 1, 6 } };
 
    int N = 3;
    int M = 7;
 
    // Function Call
    Console.Write(largestCommonSubarray(arr, N, M));
}
}
 
// This code is contributed by _saurabh_jaiswal.

2

 Complejidad temporal: O(N×M)
Espacio auxiliar: O(N×M)