LeetCode 1198 - Find Smallest Common Element in All Rows

The problem asks us to find the smallest element that appears in every row of a given m x n matrix mat, where each row is sorted in strictly increasing order. In other words, we need an element that is common to all rows and is the minimum among all such elements.

leetcodemediumarrayhash-tablebinary-searchmatrixcounting

LeetCode Problem 1198

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Matrix, Counting

Solution

Problem Understanding

The problem asks us to find the smallest element that appears in every row of a given m x n matrix mat, where each row is sorted in strictly increasing order. In other words, we need an element that is common to all rows and is the minimum among all such elements.

The input mat is a two-dimensional array of integers with m rows and n columns. Each row being strictly increasing ensures there are no duplicate elements within a row, and the values in a row are sorted from smallest to largest. The output is a single integer: the smallest element that appears in all rows, or -1 if no such element exists.

The constraints are important for understanding potential solutions. Both m and n can go up to 500, which means a naive brute-force approach that checks every element against every row could be too slow. The numbers in the matrix range from 1 to 10^4, so we might leverage this bounded range in some counting or hash-based approach.

Key edge cases include matrices where there is no common element, matrices with only one row or column, and matrices where the smallest element is not in the first column of every row.

Approaches

A brute-force approach would iterate through every element in the first row and check if it exists in all other rows. This would work correctly because it systematically tests each candidate, but it is inefficient. If we perform a linear search in each of the remaining m-1 rows for each element in the first row, the time complexity becomes O(n * m * n) which can reach O(500 * 500 * 500) = 125,000,000 operations, likely too slow for large inputs.

The key observation that allows a better solution is that every row is sorted. Because of this, we can perform a more efficient search. One optimal approach uses a hash table (or counting array) to count how many rows each number appears in. We only need to track numbers that are candidates for being common. Since the numbers are bounded up to 10^4, we can maintain a frequency counter and scan the first row to iterate in increasing order. Another approach is using multiple pointers (one for each row) to track candidates and move pointers forward efficiently, effectively merging the sorted rows.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * n) O(1) Check each element in the first row against all other rows using linear search
Optimal (Counting / Hash) O(m * n) O(10^4) Count occurrences of each number and pick the smallest with count = m

Algorithm Walkthrough

  1. Initialize a dictionary (or array) count to store the frequency of each element across all rows.
  2. Iterate through each row in the matrix.
  3. For each element in the row, if it has not been counted for the current row yet, increment its count in the dictionary.
  4. After processing all rows, iterate through the keys in sorted order (or iterate through the first row in order) and return the first element whose count equals m.
  5. If no element has a count equal to m, return -1.

Why it works: By counting the number of rows in which each element appears, we can directly determine which elements are common to all rows. Sorting or iterating in order guarantees that we find the smallest such element first.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        m = len(mat)
        count = defaultdict(int)
        
        for row in mat:
            for num in row:
                if count[num] < m:  # only increment once per row
                    count[num] += 1
        
        for num in sorted(mat[0]):
            if count[num] == m:
                return num
        return -1

The Python implementation creates a frequency dictionary to track the occurrence of each number across rows. The check count[num] < m ensures we only increment once per row, avoiding overcounting duplicates (though rows are strictly increasing, this is safe). Finally, iterating over the first row in order ensures we return the smallest common element.

Go Solution

func smallestCommonElement(mat [][]int) int {
    m := len(mat)
    count := make(map[int]int)
    
    for _, row := range mat {
        for _, num := range row {
            if count[num] < m {
                count[num]++
            }
        }
    }
    
    for _, num := range mat[0] {
        if count[num] == m {
            return num
        }
    }
    
    return -1
}

In Go, we use a map[int]int to track counts. Iterating over the first row ensures the smallest candidate is checked first. There is no need to sort because the first row is already sorted, preserving order.

Worked Examples

Example 1: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]

Step Current Row Count Table Candidate Check
1 [1,2,3,4,5] {1:1,2:1,3:1,4:1,5:1} -
2 [2,4,5,8,10] {1:1,2:2,3:1,4:2,5:2,8:1,10:1} -
3 [3,5,7,9,11] {1:1,2:2,3:2,4:2,5:3,7:1,9:1,11:1,8:1,10:1} -
4 [1,3,5,7,9] {1:2,2:2,3:3,4:2,5:4,7:2,9:2,11:1,8:1,10:1} iterate first row: 1,2,3,4,5 → first with count=4 is 5

Output: 5

Example 2: mat = [[1,2,3],[2,3,4],[2,3,5]]

Iterating the first row [1,2,3], the first element with count = 3 is 2.

Output: 2

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) We iterate through every element once to count, and iterating the first row is O(n)
Space O(10^4) Count dictionary may store every number up to the maximum 10^4

The time complexity is linear in the size of the matrix, and the space complexity is bounded by the possible range of matrix values, not by the number of elements.

Test Cases

# Provided examples
assert Solution().smallestCommonElement([[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]) == 5  # example 1
assert Solution().smallestCommonElement([[1,2,3],[2,3,4],[2,3,5]]) == 2  # example 2

# Single row
assert Solution().smallestCommonElement([[1,2,3]]) == 1  # only one row, smallest element is first

# No common element
assert Solution().smallestCommonElement([[1,2],[3,4]]) == -1  # no element appears in both rows

# Single column
assert Solution().smallestCommonElement([[1],[1],[1]]) == 1  # single column, all same

# Large numbers
assert Solution().smallestCommonElement([[10000,10001],[10000,10002]]) == 10000  # max boundary
Test Why
[[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]] validates typical multiple rows with common element
[[1,2,3],[2,3,4],[2,3,5]] ensures smallest common is found
[[1,2,3]] single row edge case
[[1,2],[3,4]] no common element scenario
[[1],[1],[1]] single column, identical elements
[[10000,10001],[10000,10002]] tests upper bound on numbers

Edge Cases

One edge case is a matrix with no common element. A naive solution might incorrectly assume the first element is common, but our implementation checks the count and correctly returns -1.

Another edge case is a single row. Any element in that row is trivially common to all rows (since there is only one). Our solution handles this because count[num] == m will automatically be satisfied for the first element.

A third edge case is large numbers at the boundary of constraints. Because our frequency dictionary uses the actual number as a key, it correctly handles elements