Elementos comunes en todas las filas de una array dada

Dada una array mxn, encuentre todos los elementos comunes presentes en todas las filas en tiempo O(mn) y un recorrido de la array.

Ejemplo: 

Input:
mat[4][5] = {{1, 2, 1, 4, 8},
             {3, 7, 8, 5, 1},
             {8, 7, 7, 3, 1},
             {8, 1, 2, 7, 9},
            };

Output: 
1 8 or 8 1
8 and 1 are present in all rows.

Una solución simple es considerar cada elemento y verificar si está presente en todas las filas. Si está presente, entonces imprímalo. 
Una mejor solución es ordenar todas las filas de la array y utilizar un enfoque similar al que se describe aquí . Ordenar tomará un tiempo O(mnlogn) y encontrar elementos comunes tomará un tiempo O(mn). Entonces, la complejidad de tiempo general de esta solución es O (mnlogn)

¿Podemos hacerlo mejor que O (mnlogn)?  
La idea es usar mapas. Inicialmente insertamos todos los elementos de la primera fila en un mapa. Para cada otro elemento en las filas restantes, verificamos si está presente en el mapa. Si está presente en el mapa y no está duplicado en la fila actual, incrementamos el recuento del elemento en el mapa en 1; de lo contrario, ignoramos el elemento. Si la fila recorrida actualmente es la última fila, imprimimos el elemento si ha aparecido m-1 veces antes. 

A continuación se muestra la implementación de la idea:

// A Program to prints common element in all
// rows of matrix
#include <bits/stdc++.h>
using namespace std;
 
// Specify number of rows and columns
#define M 4
#define N 5
 
// prints common element in all rows of matrix
void printCommonElements(int mat[M][N])
{
    unordered_map<int, int> mp;
 
    // initialize 1st row elements with value 1
    for (int j = 0; j < N; j++)
        mp[mat[0][j]] = 1;
 
    // traverse the matrix
    for (int i = 1; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // If element is present in the map and
            // is not duplicated in current row.
            if (mp[mat[i][j]] == i)
            {
               // we increment count of the element
               // in map by 1
                mp[mat[i][j]] = i + 1;
 
                // If this is last row
                if (i==M-1 && mp[mat[i][j]]==M)
                  cout << mat[i][j] << " ";
            }
        }
    }
}
 
// driver program to test above function
int main()
{
    int mat[M][N] =
    {
        {1, 2, 1, 4, 8},
        {3, 7, 8, 5, 1},
        {8, 7, 7, 3, 1},
        {8, 1, 2, 7, 9},
    };
 
    printCommonElements(mat);
 
    return 0;
}

// Java Program to prints common element in all
// rows of matrix
import java.util.*;
 
class GFG
{
 
// Specify number of rows and columns
static int M = 4;
static int N =5;
 
// prints common element in all rows of matrix
static void printCommonElements(int mat[][])
{
 
    Map<Integer,Integer> mp = new HashMap<>();
     
    // initialize 1st row elements with value 1
    for (int j = 0; j < N; j++)
        mp.put(mat[0][j],1);
         
    // traverse the matrix
    for (int i = 1; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // If element is present in the map and
            // is not duplicated in current row.
            if (mp.get(mat[i][j]) != null && mp.get(mat[i][j]) == i)
            {
                // we increment count of the element
                // in map by 1
                mp.put(mat[i][j], i + 1);
 
                // If this is last row
                if (i == M - 1)
                    System.out.print(mat[i][j] + " ");
            }
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
    int mat[][] =
    {
        {1, 2, 1, 4, 8},
        {3, 7, 8, 5, 1},
        {8, 7, 7, 3, 1},
        {8, 1, 2, 7, 9},
    };
 
    printCommonElements(mat);
}
}
 
// This code contributed by Rajput-Ji

# A Program to prints common element
# in all rows of matrix
 
# Specify number of rows and columns
M = 4
N = 5
 
# prints common element in all
# rows of matrix
def printCommonElements(mat):
 
    mp = dict()
 
    # initialize 1st row elements
    # with value 1
    for j in range(N):
        mp[mat[0][j]] = 1
 
    # traverse the matrix
    for i in range(1, M):
        for j in range(N):
             
            # If element is present in the
            # map and is not duplicated in
            # current row.
            if (mat[i][j] in mp.keys() and
                             mp[mat[i][j]] == i):
                                  
            # we increment count of the
            # element in map by 1
                mp[mat[i][j]] = i + 1
 
                # If this is last row
                if i == M - 1:
                    print(mat[i][j], end = " ")
             
# Driver Code
mat = [[1, 2, 1, 4, 8],
       [3, 7, 8, 5, 1],
       [8, 7, 7, 3, 1],
       [8, 1, 2, 7, 9]]
 
printCommonElements(mat)
 
# This code is contributed
# by mohit kumar 29

// C# Program to print common element in all
// rows of matrix to another.
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Specify number of rows and columns
static int M = 4;
static int N = 5;
 
// prints common element in all rows of matrix
static void printCommonElements(int [,]mat)
{
 
    Dictionary<int, int> mp = new Dictionary<int, int>();
     
    // initialize 1st row elements with value 1
    for (int j = 0; j < N; j++)
    {
        if(!mp.ContainsKey(mat[0, j]))
            mp.Add(mat[0, j], 1);
    }
     
    // traverse the matrix
    for (int i = 1; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // If element is present in the map and
            // is not duplicated in current row.
            if (mp.ContainsKey(mat[i, j])&&
               (mp[mat[i, j]] != 0 &&
                mp[mat[i, j]] == i))
            {
                // we increment count of the element
                // in map by 1
                if(mp.ContainsKey(mat[i, j]))
                {
                    var v = mp[mat[i, j]];
                    mp.Remove(mat[i, j]);
                    mp.Add(mat[i, j], i + 1);
                }
                else
                    mp.Add(mat[i, j], i + 1);
 
                // If this is last row
                if (i == M - 1)
                    Console.Write(mat[i, j] + " ");
            }
        }
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int [,]mat = {{1, 2, 1, 4, 8},
                  {3, 7, 8, 5, 1},
                  {8, 7, 7, 3, 1},
                  {8, 1, 2, 7, 9}};
 
    printCommonElements(mat);
}
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript Program to prints common element in all
// rows of matrix
     
    // Specify number of rows and columns
    let M = 4;
    let N =5;
     
    // prints common element in all rows of matrix
    function printCommonElements(mat)
    {
        let mp = new Map();
      
    // initialize 1st row elements with value 1
    for (let j = 0; j < N; j++)
        mp.set(mat[0][j],1);
          
    // traverse the matrix
    for (let i = 1; i < M; i++)
    {
        for (let j = 0; j < N; j++)
        {
            // If element is present in the map and
            // is not duplicated in current row.
            if (mp.get(mat[i][j]) != null && mp.get(mat[i][j]) == i)
            {
                // we increment count of the element
                // in map by 1
                mp.set(mat[i][j], i + 1);
  
                // If this is last row
                if (i == M - 1)
                    document.write(mat[i][j] + " ");
            }
        }
    }
    }
     
    // Driver code
    let mat = [[1, 2, 1, 4, 8],
       [3, 7, 8, 5, 1],
       [8, 7, 7, 3, 1],
       [8, 1, 2, 7, 9]]
       printCommonElements(mat)
     
    // This code is contributed by unknown2108
</script>

8 1 

La complejidad temporal de esta solución es O(m * n) y solo estamos haciendo un recorrido de la array.
Espacio Auxiliar : O(N)

Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.