Problem Breakdown
We are given an 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
matrepresenting a grid of integers with rows and 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: .
- Values bounded by .
- 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.
- Candidate Selection: The smallest possible answer must be present in
mat[0](the first row). If a value exists at index and satisfies the condition for all other rows, any subsequent candidate from Row 0 will be larger or equal. - Verification Strategy: Instead of checking every element against every row linearly ( per check), we use binary search (
bisect) on each remaining row to verify existence in . - 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
- Iterate through each value
candidatein the first row (mat[0]) from left to right (smallest to largest). - For each
candidate, check if it exists in every other row ( to ) using binary search:- Use
bisect_lefton row . This returns the first index where an element could be inserted. - If this index is within bounds and
row[i][index] == candidate, it exists in that row.
- Use
- Maintain a flag to track if the current
candidatewas found in all rows checked so far. - If any row fails the check, break early for that candidate and move to the next one from Row 0.
- If a candidate passes checks against all other rows, return it immediately (guaranteed minimum).
- If the loop over
mat[0]completes without returning, no common element exists; return-1.
Complexity Analysis
- Time Complexity: 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 () and perform binary search on every other row ( rows). The cost per check is . Given , this fits well within time limits (approx operations max).
- Space Complexity: 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 ( 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