Common Elements in All Rows of a Given Matrix

Understanding the Problem

The goal is to find common elements present in all rows of a given matrix.

Method 1: Using Hashing

This method uses a hash table to count occurrences of elements.

import java.util.HashMap;

public class CommonElements {
    public static void commonElements(int[][] matrix) {
        HashMap countMap = new HashMap<>();

        // Count occurrences of each element in the first row
        for (int j = 0; j < matrix[0].length; j++) {
            countMap.put(matrix[0][j], 1);
        }

        // Count occurrences in subsequent rows
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (countMap.containsKey(matrix[i][j]) && countMap.get(matrix[i][j]) == i) {
                    countMap.put(matrix[i][j], i + 1);
                }
            }
        }

        // Print common elements
        System.out.print("Common elements: ");
        for (Integer key : countMap.keySet()) {
            if (countMap.get(key) == matrix.length) {
                System.out.print(key + " ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {2, 3, 5, 6},
            {3, 4, 5, 7}
        };
        commonElements(matrix);
    }
}
            

Output:

Common elements: 3

Method 2: Using Sorting

This method sorts each row and finds common elements.

import java.util.Arrays;

public class CommonElements {
    public static void commonElements(int[][] matrix) {
        // Sort the first row
        Arrays.sort(matrix[0]);

        for (int i = 1; i < matrix.length; i++) {
            int j = 0, k = 0;
            int[] common = new int[matrix[0].length];
            int index = 0;

            // Sort the current row
            Arrays.sort(matrix[i]);

            // Find common elements
            while (j < matrix[0].length && k < matrix[i].length) {
                if (matrix[0][j] == matrix[i][k]) {
                    common[index++] = matrix[0][j];
                    j++;
                    k++;
                } else if (matrix[0][j] < matrix[i][k]) {
                    j++;
                } else {
                    k++;
                }
            }

            // Copy common elements back to the first row
            for (int m = 0; m < index; m++) {
                matrix[0][m] = common[m];
            }
            matrix[0] = Arrays.copyOf(matrix[0], index); // Update the size of the first row
        }

        // Print common elements
        System.out.print("Common elements: ");
        for (int value : matrix[0]) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {2, 3, 5, 6},
            {3, 4, 5, 7}
        };
        commonElements(matrix);
    }
}
            

Output:

Common elements: 3

Method 3: Using Set Intersection

This method uses sets to find common elements across rows.

import java.util.HashSet;

public class CommonElements {
    public static void commonElements(int[][] matrix) {
        HashSet commonSet = new HashSet<>();

        // Initialize the set with the first row
        for (int j = 0; j < matrix[0].length; j++) {
            commonSet.add(matrix[0][j]);
        }

        // Intersect with subsequent rows
        for (int i = 1; i < matrix.length; i++) {
            HashSet currentRowSet = new HashSet<>();
            for (int j = 0; j < matrix[i].length; j++) {
                currentRowSet.add(matrix[i][j]);
            }

            // Keep only common elements
            commonSet.retainAll(currentRowSet);
        }

        // Print common elements
        System.out.print("Common elements: ");
        for (Integer elem : commonSet) {
            System.out.print(elem + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {2, 3, 5, 6},
            {3, 4, 5, 7}
        };
        commonElements(matrix);
    }
}
            

Output:

Common elements: 3