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.

def common_elements(matrix):
    count_map = {}

    # Count occurrences of each element in the first row
    for j in range(len(matrix[0])):
        count_map[matrix[0][j]] = 1

    # Count occurrences in subsequent rows
    for i in range(1, len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] in count_map and count_map[matrix[i][j]] == i:
                count_map[matrix[i][j]] += 1

    # Print common elements
    print("Common elements:", end=" ")
    for key, value in count_map.items():
        if value == len(matrix):
            print(key, end=" ")
    print()

# Example usage
matrix = [
    [1, 2, 3, 4],
    [2, 3, 5, 6],
    [3, 4, 5, 7]
]
common_elements(matrix)
            

Output:

Common elements: 3

Method 2: Using Sorting

This method sorts each row and finds common elements.

def common_elements(matrix):
    # Sort the first row
    matrix[0].sort()

    for i in range(1, len(matrix)):
        j, k = 0, 0
        common = []
        
        # Sort the current row
        matrix[i].sort()

        # Find common elements
        while j < len(matrix[0]) and k < len(matrix[i]):
            if matrix[0][j] == matrix[i][k]:
                common.append(matrix[0][j])
                j += 1
                k += 1
            elif matrix[0][j] < matrix[i][k]:
                j += 1
            else:
                k += 1

        # Update the first row with common elements
        matrix[0] = common
        if not common:
            break  # No common elements found

    # Print common elements
    print("Common elements:", end=" ")
    for value in matrix[0]:
        print(value, end=" ")
    print()

# Example usage
matrix = [
    [1, 2, 3, 4],
    [2, 3, 5, 6],
    [3, 4, 5, 7]
]
common_elements(matrix)
            

Output:

Common elements: 3

Method 3: Using Set Intersection

This method uses sets to find common elements across rows.

def common_elements(matrix):
    # Initialize the set with the first row
    common_set = set(matrix[0])

    # Intersect with subsequent rows
    for i in range(1, len(matrix)):
        current_row_set = set(matrix[i])
        common_set.intersection_update(current_row_set)

    # Print common elements
    print("Common elements:", end=" ")
    for elem in common_set:
        print(elem, end=" ")
    print()

# Example usage
matrix = [
    [1, 2, 3, 4],
    [2, 3, 5, 6],
    [3, 4, 5, 7]
]
common_elements(matrix)
            

Output:

Common elements: 3