"""
Find Smallest Common Element in All Rows
    You are given an m x n matrix mat where every
    row is sorted in strictly increasing order.

    Return the smallest value that appears in every
    row. If no such value exists, return -1.

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

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

Constraints
    m == len(mat)
    n == len(mat[i])
    1 <= m, n <= 500
    1 <= mat[i][j] <= 10^4
    mat[i] is sorted in strictly increasing order

Expected Complexity
    Time  O(m * n)
    Space O(1) extra space, since values are bounded
"""

def solution(mat):
    pass


print("Find Smallest Common Element in All Rows", end=" ")
assert solution([
    [1, 2, 3, 4, 5],
    [2, 4, 5, 8, 10],
    [3, 5, 7, 9, 11],
    [1, 3, 5, 7, 9],
]) == 5, "example 1 failed"
assert solution([
    [1, 2, 3],
    [2, 3, 4],
    [2, 3, 5],
]) == 2, "example 2 failed"
assert solution([
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9],
]) == -1, "no common element failed"
assert solution([
    [1],
    [1],
    [1],
]) == 1, "single column failed"
print("OK")