Find Smallest Common Element in All Rows - Solution & Explanation

Problem Overview: You get a matrix where each row is sorted in strictly increasing order. The task is to return the smallest integer that appears in every row. If no such number exists, return -1. Because rows are sorted, smaller values appear earlier, which helps prune the search space.

Approach 1: Brute Force Row Scanning (O(m * n * m) time, O(1) space)

Start from the first row and treat each element as a candidate. For every candidate value, scan the remaining rows to check if it appears at least once. Since rows are sorted, you can stop early within a row once values exceed the candidate. This approach works but repeatedly scans rows, making it inefficient for large matrices. It mainly helps establish the baseline idea that any valid answer must come from the first row.

Approach 2: Binary Search on Each Row (O(n * m log n) time, O(1) space)

Because every row is sorted, you can iterate through elements of the first row and use binary search to check whether the value exists in each other row. If the value is present in all rows, it is a valid candidate. The first such value encountered is the smallest common element. This method leverages sorted rows and replaces linear scans with logarithmic lookups using binary search. It is reliable when row lengths are large but still performs repeated searches.

Approach 3: Counting / Frequency Tracking (O(m * n) time, O(1) space)

Traverse the entire matrix once and count how many rows each value appears in. Since rows contain strictly increasing values, a number can appear at most once per row, so simple frequency counting works. Maintain a counter array or hash map where count[x] stores how many rows contain x. Whenever a value's count reaches the number of rows m, you found a value present in every row. Track the smallest such value during the traversal.

This method treats the matrix like a stream of numbers and aggregates occurrences using a hash table or fixed-size array. It avoids repeated searches and processes each element exactly once. The algorithm fits naturally under matrix traversal combined with frequency counting.

Recommended for interviews: The counting approach is the most practical solution. It runs in linear time relative to the matrix size and keeps the implementation simple. Explaining the binary search idea first shows you recognized the sorted property, while finishing with counting demonstrates optimization and strong problem-solving instincts.