Problem

We are given a two-dimensional matrix where every row is sorted in increasing order. We need to return the smallest common element from all rows. If no common element is found, we return -1.

For instance, consider this example:

1
2
3Input: 
4[[1,2,3,4,5],
5 [2,4,5,8,10],
6 [3,5,7,9,11],
7 [1,3,5,7,9]]

The output for the above input would be 5 because 5 is the smallest number which is present in all the rows.

Approach

First, let's initialize an array, count, with size kMax + 1, where kMax is the maximum number that our elements can reach (10^4 according to the problem).

We iterate over each row in mat. For each number a in the row, we increment count[a]. If count[a] equals to the number of rows in mat, we return a as it is present in every row.

This method leverages the hash map data structure to count the occurrences of each number in all rows.

Example

Let's use the following small example to illustrate this:

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

We initialize count as a zero array of size kMax + 1.

The first row is [1,2], we iterate over it and increment count[1] and count[2].

Then, we go to the second row [1,3]. We increment count[1] and count[3]. Now, count[1] == mat.size(), which is 3, therefore, we return 1 as the smallest common element in all rows.

Solution

Python

1
2python
3class Solution:
4  def smallestCommonElement(self, mat):
5    kMax = 10000
6    count = [0] * (kMax + 1)
7
8    for row in mat:
9      for a in row:
10        count[a] += 1
11        if count[a] == len(mat):
12          return a
13
14    return -1

Java

1
2java
3public class Solution {
4  public int smallestCommonElement(int[][] mat) {
5    int kMax = 10000;
6    int[] count = new int[kMax + 1];
7
8    for(int[] row : mat) {
9      for(int a : row) {
10        count[a]++;
11        if(count[a] == mat.length) return a;
12      }
13    }
14    return -1;
15  }
16}

JavaScript

1
2javascript
3class Solution {
4  smallestCommonElement(mat) {
5    const kMax = 10000;
6    const count = new Array(kMax + 1).fill(0);
7
8    for(let row of mat) {
9      for(let a of row) {
10        count[a]++;
11        if(count[a] == mat.length) return a;
12      }
13    }
14    return -1;
15  }
16}

C++

1
2cpp
3class Solution {
4public:
5  int smallestCommonElement(vector<vector<int>>& mat) {
6    static const int kMax = 10000;
7    vector<int> count(kMax + 1);
8
9    for (const vector<int>& row : mat)
10      for (const int a : row)
11        if (++count[a] == mat.size())
12          return a;
13
14    return -1;
15  }
16};

C#

1
2csharp
3public class Solution {
4  public int SmallestCommonElement(int[][] mat) {
5    int kMax = 10000;
6    int[] count = new int[kMax + 1];
7
8    foreach(int[] row in mat) {
9      foreach(int a in row) {
10        count[a]++;
11        if(count[a] == mat.Length) return a;
12      }
13    }
14    return -1;
15  }
16}

All these solutions work with a time complexity of O(n), where n is the total number of elements in the mat. This is because we visit each number in the mat only once. The space complexity is O(k) for using a hash map (the count array), where k is the range of the possible values of the matrix elements.

The only difference between solutions in different languages is the syntax for declaring the count array and how we increment the count, but the logic remains the same.

In Python, declaration is straightforward using [0] * (kMax + 1). In Java, we use new int[kMax + 1], and for JavaScript, we need to use new Array(kMax + 1).fill(0) to fill the array with zeros. And to increment the count, in Python and JavaScript, the += operator is used, while in Java, we use ++ before the variable name.

While these solutions work for a large input size of mat and a large range of numbers, they may not be efficient for larger input. And the constraint of having all rows sorted in increasing order is not really used in these solutions.

An alternative approach would be using binary search on each row, given they are sorted. Or, if we know that the size of 'mat' is small and the maximum element is large, we could use an array to count the frequency of elements, and loop over the elements in the smallest row, checking with the array to find the first common element. However, these are more advanced solutions that may be beyond the scope of this article. For most cases, the given solutions are optimal and easy to implement and understand.