Problem Description

You are given a matrix mat with m rows and n columns. Each row in the matrix is sorted in strictly increasing order (meaning each element is larger than the previous one in the same row).

Your task is to find the smallest number that appears in every single row of the matrix. If no such number exists that appears in all rows, return -1.

For example, if you have a matrix where:

• Row 1 contains: [1, 2, 3, 4, 5]
• Row 2 contains: [2, 4, 5, 8, 10]
• Row 3 contains: [3, 5, 7, 9, 11]

The numbers that appear in all three rows are just 5. Since 5 is the only common element (and thus also the smallest), the answer would be 5.

The solution uses a counting approach. It counts how many times each number appears across all rows using a Counter. As it processes each number, it checks if that number has appeared in all rows (count equals the number of rows). Since the rows are sorted and we process them in order, the first number that appears in all rows will be the smallest common element.

The key insight is that because each row is sorted in increasing order, when we traverse the matrix row by row and element by element from left to right, the first element we encounter that has been seen in all rows must be the smallest common element.

Intuition

Since we need to find the smallest element that appears in all rows, we need to track which elements appear in each row. The straightforward approach is to count how many rows each element appears in.

The key observation is that each row is sorted in strictly increasing order. This means when we traverse the matrix row by row from left to right, we're naturally examining smaller elements before larger ones within each row.

Here's the thought process:

1. We need to check if an element appears in all rows - this suggests we need to count occurrences across rows
2. We want the smallest such element - since rows are sorted, if we process elements in order, the first element that reaches the count of len(mat) (number of rows) will be our answer
3. We can use a hash map or counter to track how many rows each element has appeared in

Why does this work? When we iterate through the matrix row by row and element by element:

• For row 1, we mark all its elements as appearing once
• For row 2, we increment counts for elements that also appeared in row 1
• This continues for all rows
• The moment any element's count reaches the total number of rows, we know it appears in every row
• Since we're processing elements in sorted order within each row, and we check the count immediately after incrementing, the first element to reach the required count is guaranteed to be the smallest common element

The beauty of this solution is that we don't need to explicitly find all common elements and then determine the minimum - the sorted nature of the rows combined with our counting approach automatically gives us the smallest one first.

Learn more about Binary Search patterns.

Solution Approach

The implementation uses a counting strategy with a hash map to track element frequencies across rows.

Data Structure Used:

• Counter(): A Python dictionary subclass that counts hashable objects. It stores elements as keys and their counts as values.

Algorithm Steps:

1. Initialize the Counter: Create an empty Counter object called cnt to track how many rows each element appears in.

2. Iterate through the matrix: Process each row sequentially:

   for row in mat:
       for x in row:

   This nested loop examines every element in the matrix, row by row, from left to right.

3. Count and Check: For each element x:

   • Increment its count: cnt[x] += 1
   • Immediately check if this element has appeared in all rows: if cnt[x] == len(mat)
   • If yes, return x immediately as it's the smallest common element

4. Return -1 if no common element: If the loops complete without finding any element that appears in all rows, return -1.

Why this works:

• Since each row is sorted in strictly increasing order, when we process elements row by row from left to right, we encounter smaller values before larger ones
• The first element whose count reaches len(mat) (the number of rows) must be the smallest element that appears in all rows
• We don't need to track which specific rows an element appears in, just the total count
• The solution has a time complexity of O(m × n) where m is the number of rows and n is the number of columns, as we visit each element once
• Space complexity is O(k) where k is the number of unique elements in the matrix

The elegance of this solution lies in leveraging the sorted property of the rows - we don't need to sort or compare elements explicitly; the traversal order naturally gives us the minimum common element first.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given matrix:

mat = [[1, 2, 5],
       [2, 4, 5],
       [3, 5, 6]]

We need to find the smallest number that appears in all 3 rows.

Step-by-step execution:

1. Initialize: Create an empty Counter cnt = {}

2. Process Row 1: [1, 2, 5]

   • Element 1: cnt[1] = 1, check if cnt[1] == 3? No (1 ≠ 3)
   • Element 2: cnt[2] = 1, check if cnt[2] == 3? No (1 ≠ 3)
   • Element 5: cnt[5] = 1, check if cnt[5] == 3? No (1 ≠ 3)
   • Counter state: {1: 1, 2: 1, 5: 1}

3. Process Row 2: [2, 4, 5]

   • Element 2: cnt[2] = 2, check if cnt[2] == 3? No (2 ≠ 3)
   • Element 4: cnt[4] = 1, check if cnt[4] == 3? No (1 ≠ 3)
   • Element 5: cnt[5] = 2, check if cnt[5] == 3? No (2 ≠ 3)
   • Counter state: {1: 1, 2: 2, 5: 2, 4: 1}

4. Process Row 3: [3, 5, 6]

   • Element 3: cnt[3] = 1, check if cnt[3] == 3? No (1 ≠ 3)
   • Element 5: cnt[5] = 3, check if cnt[5] == 3? Yes! (3 == 3)
   • Return 5 immediately

The algorithm found that 5 appears in all 3 rows and returns it as the answer. Note that we didn't need to check element 6 or look for other common elements - since rows are sorted and we process left to right, the first element reaching the required count is guaranteed to be the smallest common element.

If no element had reached a count of 3 after processing all elements, we would return -1.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of rows and n is the number of columns in the matrix. This is because the algorithm iterates through every element in the matrix exactly once - the outer loop iterates through m rows, and for each row, the inner loop iterates through n elements.

The space complexity is O(10^4) or equivalently O(1) constant space. The Counter dictionary stores at most the distinct elements that appear in the matrix. Based on the problem constraints (typical for this LeetCode problem), the values in the matrix are bounded by 1 ≤ mat[i][j] ≤ 10^4, meaning there can be at most 10^4 distinct values stored in the Counter. Since this upper bound is independent of the input size m and n, it's considered constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting Duplicate Elements Within the Same Row

The Problem: The current solution has a critical flaw - it counts duplicate elements within the same row multiple times. If a row contains duplicate values (which violates the "strictly increasing order" constraint mentioned in the problem, but could happen if the problem statement changes to "non-decreasing order"), the counter would incorrectly increment for each occurrence.

For example, if the matrix is:

• Row 1: [1, 2, 2, 3]
• Row 2: [2, 3, 4]

The element 2 would get counted twice from Row 1, giving it a total count of 3, which incorrectly suggests it appears in 3 rows when there are only 2 rows total.

Solution: Use a set to track unique elements per row before counting:

def smallestCommonElement(self, mat: List[List[int]]) -> int:
    element_count = Counter()
  
    for row in mat:
        # Convert row to set to ensure each element is counted only once per row
        unique_elements = set(row)
        for element in unique_elements:
            element_count[element] += 1
            if element_count[element] == len(mat):
                return element
  
    return -1

Pitfall 2: Not Preserving Order When Finding the Minimum

The Problem: If we modify the approach to first collect all common elements and then find the minimum, we might lose the efficiency of early termination:

# Inefficient approach
common_elements = []
for element, count in element_count.items():
    if count == len(mat):
        common_elements.append(element)
return min(common_elements) if common_elements else -1

This approach processes the entire matrix even after finding common elements and requires additional space and time to find the minimum.

Solution: Maintain the original approach of returning immediately when the first common element is found, but ensure we process elements in sorted order. One way is to process the first row completely, then only check those elements in subsequent rows:

def smallestCommonElement(self, mat: List[List[int]]) -> int:
    if not mat:
        return -1
  
    # Start with all elements from the first row as candidates
    candidates = set(mat[0])
  
    # Filter candidates by checking presence in each subsequent row
    for row in mat[1:]:
        candidates &= set(row)
        if not candidates:
            return -1
  
    # Return the minimum from remaining candidates
    return min(candidates)

Pitfall 3: Assuming Matrix Validity

The Problem: The solution doesn't handle edge cases like empty matrices or matrices with empty rows:

mat = []  # Empty matrix
mat = [[]]  # Matrix with empty row

Solution: Add validation at the beginning:

def smallestCommonElement(self, mat: List[List[int]]) -> int:
    if not mat or not all(row for row in mat):
        return -1
  
    element_count = Counter()
    # ... rest of the solution