NeetCode #26LC-1198MediumArrays & HashingNC Algo100
← Back to All Problems#26 · #1198 · Find Smallest Common Element in All Rows(找出所有行中最小的公共元素)
📌 Problem Statement & Constraints
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. Constraints: 1 <= m, n <= 500, 1 <= mat[i][j] <= 10^4, each row is strictly increasing.💡 Core Algorithmic Approaches
- A value is common to all rows only if it appears in every row. Count, for each value, how many rows contain it.
- Use a hash map from value to the number of rows containing it. Iterate each row and add 1 per distinct value in that row (the rows are strictly increasing, so no value repeats within a row).
- Then find the smallest value whose row count equals
m. - Because the rows are sorted, an alternative is a k-way merge with a heap or a pointer per row, but the counting approach is simpler and O(m * n).
💻 Benchmark Python3 Implementation
class Solution:
def smallestCommonElement(self, mat: List[List[int]]) -> int:
from collections import defaultdict
rows = len(mat)
cnt = defaultdict(int)
for row in mat:
for v in row: # strictly increasing -> no duplicates
cnt[v] += 1
best = -1
for v in sorted(cnt): # ascending order -> first hit is the answer
if cnt[v] == rows:
best = v
break
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n + V log V): the counting pass is O(m * n) and sorting the distinct values is O(V log V) with V <= 10^4. A k-way merge would be O(m * n * log m).
💾 Space Complexity
O(V) for the counter, V <= 10^4.
⚠️ Interview Pitfalls & Follow-ups
- Counting occurrences rather than rows: within a row, each value appears once (strictly increasing), so the distinction does not bite here -- but if rows could contain duplicates, you would need to deduplicate per row.
- Iterating
cntin insertion order and taking the first match: the first match in insertion order is not necessarily the smallest value. Sort the keys. - Assuming the answer must be in the first row's first element: it can be any value.
- Using a set intersection of all rows: correct and concise, but it loses the count information and is O(m * n) with a larger constant.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.