Find Smallest Common Element in All Rows

Find Smallest Common Element in All Rows

What is this problem about?

The Find Smallest Common Element in All Rows interview question asks you to find the smallest integer that appears in every single row of an $m imes n$ matrix. If no such element exists, return -1. Each row is typically sorted in strictly increasing order.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask this to evaluate your proficiency with Matrix interview patterns and Binary Search. It evaluations if you can leverage the "sorted rows" property to optimize the search from $O(M imes N)$ to something faster, or use a frequency map for a simple linear approach.

Algorithmic pattern used

There are three common ways to solve this:

1. Frequency Counting: Use a hash map or array to count occurrences of each number. The first number that reaches a count of $M$ (total rows) is the smallest common element.
2. Binary Search: For every element in the first row, check if it exists in all other rows using binary search ($O(N imes M \log N)$).
3. Row Pointers: Maintain $M$ pointers, one for each row. Repeatedly increment the pointers of rows whose current element is smaller than the maximum current element across all rows.

Example explanation

Matrix:

1 2 3 4
2 3 5 8
2 4 5 6

• First element of Row 0: 1. Is it in Row 1? No.
• Second element of Row 0: 2. Is it in Row 1? Yes. Is it in Row 2? Yes. Result: 2.

Common mistakes candidates make

• Ignoring Sorted Property: Not using binary search or pointers, leading to a less efficient solution than expected.
• Early Exit: Returning an element that is common to some rows but not all.
• Inefficient Counting: Using a large map when the range of values is small enough for a simple frequency array.

Interview preparation tip

Whenever you have "multiple sorted lists" and need to find an intersection, think about the Pointers approach or Binary Search. This is a fundamental Array interview pattern that appears in many variations (like "Intersection of Three Sorted Arrays").