Problem link - Find Common Element in
Problem Statement:
You are given a matrix of integers with R rows and C columns. Your task is to find the smallest common element that appears in all rows of the matrix. If there are multiple common elements, return the smallest one. If no common element exists, return -1.
Approach:
To solve this problem, we need to track which elements appear in all rows of the matrix and find the smallest one among them.
Key Idea:
We can use a hash map (or dictionary) to count how many rows each element appears in. Initially, we will store all the elements from the first row in this hash map and assume they are potential candidates for being common elements across all rows. Then, for each subsequent row, we will update the map to keep track of how many rows each element has appeared in.
Step-by-Step Explanation:
-
Initialize a Hash Map:
- First, we create a hash map to store elements from the first row of the matrix. For each element, we set its initial count to 1 since we start by assuming it appears in the first row.
- For example, if the first row is [1, 2, 3], the map would store: {1: 1, 2: 1, 3: 1}.
-
Process the Remaining Rows:
- We now go through each of the remaining rows in the matrix.
- For every element in each row, we check if it exists in the map. If it does, and if it has already been counted as appearing in all previous rows, we increase its count in the map.
- For example, if the second row is [2, 3, 4], after processing this row, the map will become: {1: 1, 2: 2, 3: 2}. Notice that only elements 2 and 3 have their counts updated because they are common between the first two rows.
-
Identify Common Elements:
- Once we’ve processed all the rows, we now check for elements that have appeared in every row. This can be identified by looking at the counts in the hash map. If the count of an element is equal to R (the total number of rows), it means that this element appears in all rows.
- For example, if after processing all rows, the map looks like {1: 1, 2: 3, 3: 3}, it means that elements 2 and 3 are present in all rows (since their counts match the number of rows, which is 3).
-
Find the Smallest Common Element:
- From the elements that appear in all rows, we select the smallest one. If no element appears in all rows, we return -1.
-
Return the Result:
- If we find any common element, we return the smallest one. If no common element is found (meaning no element has a count equal to R), we return -1.
Time Complexity:
- The time complexity is O(R * C). This is because we go through every element in the matrix and check or update the hash map in constant time.
Space Complexity:
- The space complexity is O(C). At most, we are storing the elements from one row in the hash map, which takes space proportional to the number of columns.