⚡Flashcard Drill➔
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

  1. A value is common to all rows only if it appears in every row. Count, for each value, how many rows contain it.
  2. 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).
  3. Then find the smallest value whose row count equals m.
  4. 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 cnt in 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems