[LeetCode] Find Smallest Common Element in All Rows

Problem: Given a matrix mat where every row is sorted in strictly increasing order, return the smallest common element in all rows.

If there is no common element, return -1.

Example:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

Approach: The thing to catch here is every row is sorted in strictly increasing order that means there will be no duplicates in a row. We can use this fact.

If we count the occurrences of every element in the matrix and whenever we find the count of element is equal to the number of rows that means this element is common to all rows. Now we just need to find out the minimum of such elements.

We can calculate frequency using a hash table.

Implementation in C#:

    public int SmallestCommonElement(int[][] mat) 

    {

        Dictionary<int, int> freqMap = new Dictionary<int, int>();

        for (int i = 0; i < mat.Length; ++i)

        {

            for (int j = 0; j < mat[0].Length; ++j)

            {

                if (!freqMap.ContainsKey(mat[i][j]))

                {

                    freqMap[mat[i][j]] = 0;

                }

                

                ++freqMap[mat[i][j]];

            }

        }

        int min = int.MaxValue;

        foreach(var entry in freqMap)

        {

            if (entry.Value == mat.Length)

            {

                min = min > entry.Key ? entry.Key : min;

            }

        }

        return min == int.MaxValue ? -1 : min;

    }

Complexity: O(m * n) m is number of rows and n is number of columns