Java Program to Find Common Elements in All Rows of a Given Matrix

Problem Description

A matrix consisting of 'm' rows and 'n' columns is shown to you. The purpose is to identify the items that are common to all rows of the matrix. The solution should efficiently return these common elements, considering both time and space complexity.

Approach

To solve this problem, we use a hash-based solution. We maintain a hash map (or hash table) to track the frequency of each element across the rows. The algorithm involves the following steps:

1. Initialization: Create a 'HashMap<Integer, Integer>' to hold entries and their counts. The key is the element, and the value is the number of rows in which it appears.
2. Process the First Row: Traverse the first row of the matrix and store each element in the hash map with a count of 1.
3. Processing Subsequent Rows: For each subsequent row, update the count of elements only if they are already present in the hash map and have appeared in all previous rows.
   Remove elements from the map if they are not found in the current row, ensuring only the common elements remain by the end of processing.
4. Final Check: At the end, iterate through the hash map to find elements whose count matches the number of rows. These are the common elements.

File Name: CommonElementsMatrix.java

Output:

 
Common elements in all rows: [1,8]   

Explanation

The Java code begins by defining the findCommonElements() function that takes a 2D integer array (matrix) as input. First, the code checks if the matrix is empty or null to handle edge cases. A hash map (map) is initialized to track the frequency of elements from the matrix's rows.

The first row's elements are added to the map with an initial count of 1. For each subsequent row, the code only updates the counts for elements that were present in all previous rows using a temporary map (TempMap). If an element's count matches the row index, it indicates that the element is present in all rows up to that point.

Finally, the elements that maintain the count equivalent to the total number of rows are considered common and added to the result list.

Complexity Analysis

Initialization of the hash map for the first row takes (O(n)), where (n) is the number of columns. Processing the rows takes (O(m times n)) where (m) is the number of rows, as each element in the matrix is checked once. The Final collection of common elements takes (O(k)), where (k) is the number of common elements.

Thus, the overall time complexity is (O(m times n)).

Space Complexity Analysis

The space required for storing elements in the hash map is (O(n)) for the worst case (if all elements are unique in the first row). Additional space for storing temporary results during row processing. Hence, the space complexity is (O(n)).

In the provided example, 1 and 8 are the only elements that appear in all rows of the matrix. The algorithm efficiently identifies 1 and 8 by updating counts row by row and filtering out non-common elements.

Advantages of the Approach

• Efficiency: The algorithm avoids redundant checks by updating counts only for relevant elements.
• Simplicity: It uses basic data structures like HashMap, making the implementation straightforward.
• Scalability: Works well for larger matrices as it linearly processes each row.

Alternative Approaches

1. Sorting-Based Approach: Each row can be sorted, and a common element search using binary search could be implemented. However, this increases complexity to (O(m times n log n)).
2. Set-Based Approach: Use HashSet for each row and compute the intersection iteratively. The complexity is similar to the hash-based approach but may use additional space for multiple sets.

Conclusion

The hash-based approach used in this code is optimal for finding common elements across rows of a matrix, maintaining a balance between simplicity and efficiency.