Domain 2MediumMEDIUM

Find Smallest Common Element in All Rows

Iterate through elements of the first row in ascending order, using binary search to verify existence in all other rows; return the first match or -1.

Domain: medium•Updated: 2026-09-10
#Binary Search#Matrix Traversal#$O(N cdot M log N)$#$O(1) Space$

Problem Breakdown

We are given an m×nm \times n matrix mat where each row is sorted strictly increasing. We need to find the smallest integer that appears in every single row (the intersection of all rows). If no such element exists, we return -1.

  • Inputs: A 2D list mat representing a grid of integers with mm rows and nn columns.
  • Outputs: The minimum common integer across all rows, or -1.
  • Constraints & Edge Cases:
    • Rows are strictly increasing (no duplicates within a row).
    • Matrix dimensions: 1≤m,n≤5001 \le m, n \le 500.
    • Values bounded by 10410^4.
    • Must handle cases where no common element exists or the matrix has only one column/row.

Intuition

The problem asks for an intersection of multiple sorted arrays. Since every row is sorted, we can leverage this property to avoid linear scans on all rows repeatedly.

  1. Candidate Selection: The smallest possible answer must be present in mat[0] (the first row). If a value exists at index jj and satisfies the condition for all other rows, any subsequent candidate from Row 0 will be larger or equal.
  2. Verification Strategy: Instead of checking every element against every row linearly (O(N)O(N) per check), we use binary search (bisect) on each remaining row to verify existence in O(log⁡N)O(\log N).
  3. Early Exit: Since mat[0] is sorted, the first candidate that passes verification for all other rows is guaranteed to be the smallest common element. We can return immediately upon finding it.

Approach

  1. Iterate through each value candidate in the first row (mat[0]) from left to right (smallest to largest).
  2. For each candidate, check if it exists in every other row (i=1i = 1 to m−1m-1) using binary search:
    • Use bisect_left on row ii. This returns the first index where an element ≥candidate\ge candidate could be inserted.
    • If this index is within bounds and row[i][index] == candidate, it exists in that row.
  3. Maintain a flag to track if the current candidate was found in all rows checked so far.
  4. If any row fails the check, break early for that candidate and move to the next one from Row 0.
  5. If a candidate passes checks against all other rows, return it immediately (guaranteed minimum).
  6. If the loop over mat[0] completes without returning, no common element exists; return -1.

Complexity Analysis

  • Time Complexity: O(N⋅Mlog⁡N)O(N \cdot M \log N) in the worst case where a solution is found at the end of Row 0 or does not exist. We iterate through each column index (NN) and perform binary search on every other row (M−1M-1 rows). The cost per check is log⁡(row_length)\log(\text{row\_length}). Given m,n≤500m, n \le 500, this fits well within time limits (approx 2.5×1062.5 \times 10^6 operations max).
  • Space Complexity: O(1)O(1) auxiliary space if we ignore the input storage. We do not store a frequency map or pointers for all rows, making it memory efficient compared to hash-map based solutions (O(MN)O(MN) worst case unique elements in Python dict overhead).

Solution

import bisect

def smallestCommonElement(mat):
    """
    Finds the smallest common element across strictly increasing sorted rows.
    
    Args:
        mat (List[List[int]]): Matrix where each row is sorted strictly increasing.
        
    Returns:
        int: The smallest integer present in every row, or -1 if none exists.
    """
    m = len(mat)
    
    # Handle edge case for empty matrix based on constraints usually implying valid input (m >= 1)
    if not mat or m == 0: 
        return -1
        
    n = len(mat[0])

    # Iterate through the first row to get candidates in ascending order.
    # Since Row 0 is sorted strictly increasing, we check smallest values first.
    for candidate in mat[0]:
        common_in_all_rows = True
        
        # Check existence of 'candidate' in every other row using binary search (bisect)
        for i in range(1, m):
            idx = bisect.bisect_left(mat[i], candidate)
            
            # If the insertion point is out of bounds or value doesn't match exactly:
            if idx == len(mat[i]) or mat[i][idx] != candidate:
                common_in_all_rows = False
                break
        
        # Since we iterate Row 0 from left to right, the first valid 'candidate' 
        # that passes all checks is guaranteed to be the smallest possible answer.
        if common_in_all_rows:
            return candidate
            
    # If no element in mat[0] exists in all other rows
    return -1