Find Smallest Common Element in All Rows solution and explanation
9 more videos on this problem
LeetCode 1198: Find Smallest Common Element in All Rows - Interview Prep Ep 9Fisher Coder · 13:03 · 3K views
1198 Find Smallest Common Element in All RowsKelvin Chandra · 4:52 · 1K views
8. Smallest common element in all rows ( Leet code problem no.1198)CSE GURUS · 25:24 · 1K views
1198. Find Smallest Common Element in All Rows - Week 1/5 Leetcode November ChallengeProgramming Live with Larry · 4:42 · 447 views
LeetCode 1198. Find Smallest Common Element in All Rows | JSer - JavaScript & AlgorithmJSer · 6:19 · 323 views
1198. Find Smallest Common Element in All Rows - Week 2/5 Leetcode August ChallengeProgramming Live with Larry · 5:16 · 292 views
1198. Find Smallest Common Element in All RowsProgrammer Fellas · 6:13 · 229 views
Leetcode Find Smallest Common Element in All Rows MediumLester Minnick · 8:35 · 104 views
LeetCode 1198 | Find Smallest Common Element in All Rows | Counting Array | JavaSleepy Cracker · 3:23 · 99 views
1198. Find Smallest Common Element in All RowsMuerde un zombie · 5:43 · 61 views
The problem
Given an m x n 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 1:
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]] Output: 5
Example 2:
Input: mat = [[1,2,3],[2,3,4],[2,3,5]] Output: 2
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 5001 <= mat[i][j] <= 104mat[i]is sorted in strictly increasing order.
Approach overview
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.
Solution
We use an array cnt of length 10001 to count the frequency of each number. We sequentially traverse each number in the matrix and increment its frequency. When the frequency of a number equals the number of rows in the matrix, it means that this number appears in each row, and thus it is the smallest common element. We return this number.
If we do not find the smallest common element after the traversal, we return -1.
The time complexity is O(m times n), and the space complexity is O(10^4). Here, m and n are the number of rows and columns in the matrix, respectively.
class Solution:
def smallestCommonElement(self, mat: List[List[int]]) -> int:
cnt = Counter()
for row in mat:
for x in row:
cnt[x] += 1
if cnt[x] == len(mat):
return x
return -1class Solution {
public int smallestCommonElement(int[][] mat) {
int[] cnt = new int[10001];
for (var row : mat) {
for (int x : row) {
if (++cnt[x] == mat.length) {
return x;
}
}
}
return -1;
}
}class Solution {
public:
int smallestCommonElement(vector<vector<int>>& mat) {
int cnt[10001]{};
for (auto& row : mat) {
for (int x : row) {
if (++cnt[x] == mat.size()) {
return x;
}
}
}
return -1;
}
};function smallestCommonElement(mat: number[][]): number {
const cnt: number[] = new Array(10001).fill(0);
for (const row of mat) {
for (const x of row) {
if (++cnt[x] == mat.length) {
return x;
}
}
}
return -1;
}func smallestCommonElement(mat [][]int) int {
cnt := [10001]int{}
for _, row := range mat {
for _, x := range row {
cnt[x]++
if cnt[x] == len(mat) {
return x
}
}
}
return -1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Row Scanning | O(m * n * m) | O(1) | Understanding the baseline idea or when matrix sizes are very small |
| Binary Search per Candidate | O(n * m log n) | O(1) | When rows are sorted and you want faster membership checks |
| Counting / Frequency Tracking | O(m * n) | O(1) | Best general solution; processes each element once and finds the smallest common value efficiently |
Frequently asked questions
Is Find Smallest Common Element in All Rows easy or hard?
The problem is rated Medium because the idea is simple but requires recognizing how to efficiently check presence across multiple rows. A naive scan works but is slow, while the optimal counting solution processes the matrix once and uses frequency tracking.
Find Smallest Common Element in All Rows Python/Java solution
In Python or Java, implement a counting array or HashMap to track how many rows contain each value. Iterate through the matrix and update the count for each element. When a value's count equals the total number of rows, return it as the smallest common element. The implementation runs in O(m * n) time.
How to solve Find Smallest Common Element in All Rows in O(m*n)?
Use a frequency counter while scanning the matrix. For every value encountered, increment its count in an array or hash map. When the count reaches the total number of rows, that value exists in every row. Track the minimum such value while iterating to ensure the smallest common element is returned.
What is the best approach for Find Smallest Common Element in All Rows?
The counting (frequency tracking) approach is typically the best solution. Traverse every element in the matrix and maintain a count of how many rows contain each value. When a value's frequency equals the number of rows, it appears in every row. This runs in O(m * n) time and avoids repeated searches.
Is Find Smallest Common Element in All Rows asked at Google/Amazon/Meta?
Matrix traversal and frequency-counting problems like this appear in interviews at large tech companies including Google, Amazon, and Meta. The problem tests understanding of sorted structures, hash-based counting, and efficient scanning of 2D arrays.
What data structure is used in Find Smallest Common Element in All Rows?
The main data structure is a frequency counter implemented using either a hash table or a fixed-size counting array. The matrix itself is traversed row by row. Some alternative solutions also use binary search on sorted rows.
What is the time complexity of Find Smallest Common Element in All Rows?
The optimal counting solution runs in O(m * n) time where m is the number of rows and n is the number of columns. Each matrix element is processed once. Space complexity is O(1) if a fixed-size counting array is used, since values are bounded by the problem constraints.