10. Common elements of all the rows of the Matrix

10. Common elements of all the rows of the Matrix

Problem link :- click here

package progams;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Matrix__10
{

	/*
	    Given an N x N matrix, find all common elements present in all rows in O(mn) time and one traversal of matrix
	    
	    				1    	2    	1    	4    	8
	    				3    	7    	8    	5    	1
	    				8    	7    	7    	3    	1
	    				8    	1    	2    	7    	9
	    			
	    	here  8   and    1     are the elements that has repeated in all rows.
	    	
	    	lets put() all the elements of first to a hash-map.
	    			key -> element              value -> number of times repeated
	    	while iterating through all the rows from first row             
	    	 	we will check if the element is present in the hash-map
	    	 	and also we need to check that the element as repeated exactly number of rows checked(including first row)
	    	 	because there is a possibility that the element has repeated in a row
	    	 		if the element obeys the above condition then 
	    	 		we will increment the value(number of times repeated)
	    	 after the loop finishes its job,  we will check which elements has repeated 'row' number of times
	    	 and print those elements
	*/
	
	static void commonElements(int mat[][], int r, int c)
	{
		Map<Integer, Integer> map = new HashMap<>();
		
		//adding all the elements to the hash-map
		for(int i=0; i<c; i++)
		{
			if(  !map.containsKey( mat[0][i] )  )
				map.put(mat[0][i], 1);
		}
		
		//iterating through the array
		for(int i=1; i<r; i++)
		{
			for(int j=0; j<c; j++)
			{
				/*
				 	if map.get( mat[i][j] == i )      is the first condition then it would through an error
				 		when mat[i][j]  is not present in the matrix
				 	as we are using    &&  (logical and)   we will not get any error 
				 	because it checks the 1st condition and if that condition is true then only it checks the 
				 		2nd condition other-wise it doesn't checks (so we don't get any error)
				 */
				
				if( map.containsKey( mat[i][j] )      &&     map.get( mat[i][j] ) == i    )
					map.put( mat[i][j], map.get(mat[i][j]) +1 );
			}
		}
		
		//printing the elements that are present in each row
		//we will check how of the elements of first row is present in all rows and print that
		for(int i=0; i<c; i++)
		{
			if( map.get( mat[0][i] )   ==    r )
			{
				System.out.print(mat[0][i] + " ");
				
				/*
				      	if any element which is repeated in all row    
				 		has occurred more than once in the first row then it will be printed more than once
				 	in the above example '1' has occurred twice in the first row so it will  be printed twice
				 	to avoid this we will increment the value of that key so it comes to check the condition 
				 	  	and the condition will fail so that element is not printed
				 */		
				map.put(    mat[0][i],   map.get( mat[0][i] ) + 1    );
			}
		}
	}
	
	public static void main(String[] args)
	{
		int i, j, r, c;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the number of rows : ");
		r = s.nextInt();
		System.out.print("Enter the numvber of columns : ");
		c = s.nextInt();
		int matrix[][] = new int[r][c];
		System.out.println("Enter the elements of the matrix : ");
		for(i=0; i<r; i++)
		{
			for(j=0; j<c; j++)
				matrix[i][j] = s.nextInt();
		}
		System.out.println("Given matrix : ");
		printMatrix(matrix, r, c);

		System.out.println("\n\nElements which are present in all rows is : ");
		System.out.print("\t\t\t");
		commonElements(matrix, r, c);
	}

	static void printMatrix(int mat[][], int r, int c)
	{
		for(int i=0; i<r; i++)
		{
			for(int j=0; j<c; j++)
				System.out.print(mat[i][j] + "  ");
			System.out.println();
		}
	}
}

Time complexity :- O(r*c)
Space complexity :- O(c)