Problem Description

You are given a 2D integer array mat where each row is sorted in strictly increasing order. Your task is to find the smallest common element present in all rows of mat. If there is no such common element, return -1.

• Each row in mat is sorted in strictly increasing order.
• All elements are positive integers.
• There may be no common element among all rows, in which case you must return -1.
• You cannot reuse elements; each element can only be counted once per row.

Thought Process

To solve this problem, we need to find an integer that appears in every row of the matrix. The brute-force approach would be to check every element in the matrix against all rows, but this is inefficient, especially for large matrices.

Instead, we can take advantage of the fact that each row is sorted in strictly increasing order. This means we can use more efficient searching techniques, such as using pointers or hash maps to keep track of element occurrences.

The initial idea is: for each element in the first row, check if it exists in all other rows. If we find such an element, it is a candidate for the answer. We want the smallest such element, so we process the first row from left to right.

However, this can still be improved. By using hash maps or pointers, and leveraging the sorted nature of the rows, we can avoid unnecessary checks and make the process much faster.

Solution Approach

Let's break down the optimized approach step by step:

1. Use a Hash Map (or Counter):
   • We can count the occurrence of each number across all rows. If a number appears in all rows, it must have a count equal to the number of rows.
   • Since the rows are sorted, we can process each row and add each element to the hash map or counter.
2. Optimize with Pointers:
   • Because each row is sorted, we can use pointers (indices) for each row and move them forward in a coordinated way, similar to merging K sorted lists.
   • We initialize a pointer for each row at index 0.
   • At each step, we find the maximum value among the current elements pointed to by the pointers.
   • We move forward all pointers that point to values less than the maximum, since those values cannot be common to all rows.
   • If all pointers point to the same value, we've found the smallest common element.
   • If any pointer reaches the end of its row, and we haven't found a common element, we return -1.
3. Why This Works:
   • We always move the pointer(s) with the smallest value forward, ensuring we never miss a possible common element.
   • Because the rows are sorted, we never need to look back.

Example Walkthrough

Let's use the following example:

  mat = [
    [1, 2, 3, 4, 5],
    [2, 4, 5, 8, 10],
    [4, 5, 8, 9, 10]
  ]
  

• Initialize pointers at index 0 for each row: [1, 2, 4]
• Maximum among these is 4.
• Move pointers forward in rows where the value is less than 4:
• First row: move from 1 to 2 to 3 to 4 (index 3).
• Second row: move from 2 to 4 (index 1).
• Third row: already at 4 (index 0).
• Now, pointers are at [4, 4, 4] (indices [3,1,0]).
• All pointers point to 4. This is the smallest common element.
• Return 4.

If there is no such common element, the pointers will eventually reach the end of a row and we return -1.

Time and Space Complexity

Brute-force approach:

• For each element in the first row (n elements), check if it exists in all other rows (m rows, each of length up to n), using binary search (O(log n)) or linear search (O(n)).
• Time complexity: O(m * n * log n) (if using binary search for each row).
• Space complexity: O(1), or O(n) if using extra data structures.

• At most, we make O(m * n) moves, as each pointer only moves forward and each row has n elements.
• Time complexity: O(m * n) in the worst case, but often much less in practice.
• Space complexity: O(m) for the pointers.

Summary

By leveraging the sorted property of each row, we can efficiently find the smallest common element using pointers, similar to merging sorted lists. This approach avoids unnecessary work and ensures we find the answer as quickly as possible, or determine that no common element exists. The key insight is to always move forward the pointers with the smallest current value, and check for equality across all rows at each step.

Code Implementation

class Solution:
    def smallestCommonElement(self, mat):
        m, n = len(mat), len(mat[0])
        pointers = [0] * m
        while True:
            current = [mat[i][pointers[i]] for i in range(m)]
            max_val = max(current)
            # If all values are equal, found the common element
            if all(val == max_val for val in current):
                return max_val
            # Advance pointers which are less than max_val
            for i in range(m):
                while pointers[i] < n and mat[i][pointers[i]] < max_val:
                    pointers[i] += 1
                if pointers[i] == n:
                    return -1

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> pointers(m, 0);
        while (true) {
            int max_val = mat[0][pointers[0]];
            for (int i = 1; i < m; ++i)
                max_val = max(max_val, mat[i][pointers[i]]);
            bool all_equal = true;
            for (int i = 0; i < m; ++i)
                if (mat[i][pointers[i]] != max_val)
                    all_equal = false;
            if (all_equal)
                return max_val;
            for (int i = 0; i < m; ++i) {
                while (pointers[i] < n && mat[i][pointers[i]] < max_val)
                    pointers[i]++;
                if (pointers[i] == n)
                    return -1;
            }
        }
    }
};

class Solution {
    public int smallestCommonElement(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] pointers = new int[m];
        while (true) {
            int maxVal = mat[0][pointers[0]];
            for (int i = 1; i < m; i++)
                maxVal = Math.max(maxVal, mat[i][pointers[i]]);
            boolean allEqual = true;
            for (int i = 0; i < m; i++) {
                if (mat[i][pointers[i]] != maxVal)
                    allEqual = false;
            }
            if (allEqual)
                return maxVal;
            for (int i = 0; i < m; i++) {
                while (pointers[i] < n && mat[i][pointers[i]] < maxVal)
                    pointers[i]++;
                if (pointers[i] == n)
                    return -1;
            }
        }
    }
}

var smallestCommonElement = function(mat) {
    let m = mat.length, n = mat[0].length;
    let pointers = new Array(m).fill(0);
    while (true) {
        let current = pointers.map((ptr, i) => mat[i][ptr]);
        let maxVal = Math.max(...current);
        if (current.every(val => val === maxVal))
            return maxVal;
        for (let i = 0; i < m; ++i) {
            while (pointers[i] < n && mat[i][pointers[i]] < maxVal)
                pointers[i]++;
            if (pointers[i] === n)
                return -1;
        }
    }
};