Solution Explanation: Finding the Smallest Common Element in All Rows

The problem asks to find the smallest element that is common to all rows of a given matrix where each row is sorted in strictly increasing order. The optimal approach leverages the sorted nature of the rows and uses a frequency counting technique to efficiently find the solution.

Approach: Counting Frequency

1. Initialization: We initialize a frequency array cnt (or a hash map in some languages) of size 10001 (as per the problem constraints, the maximum element value is 104). This array will store the frequency of each number encountered in the matrix. We can safely use a fixed-size array since the range of numbers is limited.

2. Iterating Through the Matrix: We iterate through each row of the matrix, and within each row, we iterate through each element x.

3. Incrementing Frequency: For each element x, we increment its frequency count in the cnt array: cnt[x]++.

4. Checking for Common Element: After incrementing the frequency, we check if the frequency count of x is equal to the number of rows in the matrix (len(mat) or mat.length). If it is, it means that x appears in all rows. Since we are iterating through the matrix in order, the first such x encountered will be the smallest common element. We immediately return this value.

5. No Common Element: If the loop completes without finding any element with a frequency equal to the number of rows, it implies that there's no common element in all rows. In this case, we return -1.

Time and Space Complexity Analysis

• Time Complexity: O(m*n), where 'm' is the number of rows and 'n' is the number of columns in the matrix. This is because we iterate through each element of the matrix exactly once.

• Space Complexity: O(1). While we use a frequency array cnt, its size is fixed and independent of the input matrix dimensions. Therefore, it's considered constant space complexity. In languages supporting hash maps, the space complexity would be O(k) where k is the number of unique elements which is at most min(m*n, 10000). However, in the given context with a fixed upper bound of 10000 this is also considered O(1).

Code Examples in Different Languages

The code implementations below follow the explained algorithm. Note that the choice of Counter in Python and the use of a fixed-size array in other languages are optimized for this specific problem's constraints. For larger ranges of numbers, a hash map would be a more general solution.

Python3

from collections import Counter
 
class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        cnt = Counter()
        for row in mat:
            for x in row:
                cnt[x] += 1
                if cnt[x] == len(mat):
                    return x
        return -1

Java

class Solution {
    public int smallestCommonElement(int[][] mat) {
        int[] cnt = new int[10001];
        for (int[] row : mat) {
            for (int x : row) {
                if (++cnt[x] == mat.length) {
                    return x;
                }
            }
        }
        return -1;
    }
}

C++

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        int cnt[10001] = {}; // Initialize to 0
        for (auto& row : mat) {
            for (int x : row) {
                if (++cnt[x] == mat.size()) {
                    return x;
                }
            }
        }
        return -1;
    }
};

Go

func smallestCommonElement(mat [][]int) int {
	cnt := [10001]int{}
	for _, row := range mat {
		for _, x := range row {
			cnt[x]++
			if cnt[x] == len(mat) {
				return x
			}
		}
	}
	return -1
}

JavaScript

/**
 * @param {number[][]} mat
 * @return {number}
 */
var smallestCommonElement = function(mat) {
    const cnt = new Array(10001).fill(0);
    for (const row of mat) {
        for (const x of row) {
            cnt[x]++;
            if (cnt[x] === mat.length) return x;
        }
    }
    return -1;
};

TypeScript

function smallestCommonElement(mat: number[][]): number {
    const cnt: number[] = new Array(10001).fill(0);
    for (const row of mat) {
        for (const x of row) {
            cnt[x]++;
            if (cnt[x] === mat.length) return x;
        }
    }
    return -1;
}

These code examples demonstrate the efficient solution using frequency counting, achieving optimal time complexity. Remember that the constant-size array approach is suitable only due to the problem's constraints. For more general scenarios, a hash map would be more appropriate to handle a wider range of input values.