1198. Find Smallest Common Element in All Rows

leetcode medium

#array#csharp#leetcode#matrix#medium#search#sort#string

Task

Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.

Если общего элемента нет, верните -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

C# solution

matched/original

public class Solution {
    public int SmallestCommonElement(int[][] mat) {
        int n = mat.Length, m = mat[0].Length;
        int[] pos = new int[n];
        int cur_max = 0, cnt = 0;
        
        while (true) {
            for (int i = 0; i < n; ++i) {
                while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                    ++pos[i];
                }
                if (pos[i] >= m) {
                    return -1;
                }
                if (mat[i][pos[i]] != cur_max) {
                    cnt = 1;
                    cur_max = mat[i][pos[i]];
                } else if (++cnt == n) {
                    return cur_max;
                }
            }
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SmallestCommonElement(int[][] mat) {
        int n = mat.size(), m = mat[0].size();
        vector<int>& pos = new int[n];
        int cur_max = 0, cnt = 0;
        
        while (true) {
            for (int i = 0; i < n; ++i) {
                while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                    ++pos[i];
                }
                if (pos[i] >= m) {
                    return -1;
                }
                if (mat[i][pos[i]] != cur_max) {
                    cnt = 1;
                    cur_max = mat[i][pos[i]];
                } else if (++cnt == n) {
                    return cur_max;
                }
            }
        }
    }
}

Java solution

matched/original

public int smallestCommonElement(int[][] mat) {
    int n = mat.length, m = mat[0].length;
    int pos[] = new int[n], cur_max = 0, cnt = 0;
    while (true) {
        for (int i = 0; i < n; ++i) {
            while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                ++pos[i];
            }
            if (pos[i] >= m) {
                return -1;
            }
            if (mat[i][pos[i]] != cur_max) {
                cnt = 1;
                cur_max = mat[i][pos[i]];
            } else if (++cnt == n) {
                return cur_max;
            }
        }
    }
}

JavaScript solution

matched/original

class Solution {
    smallestCommonElement(mat) {
        const n = mat.length;
        const m = mat[0].length;
        const pos = new Array(n).fill(0);
        let cur_max = 0;
        let cnt = 0;
        
        while (true) {
            for (let i = 0; i < n; ++i) {
                while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                    ++pos[i];
                }
                if (pos[i] >= m) {
                    return -1;
                }
                if (mat[i][pos[i]] !== cur_max) {
                    cnt = 1;
                    cur_max = mat[i][pos[i]];
                } else if (++cnt === n) {
                    return cur_max;
                }
            }
        }
    }
}

Python solution

matched/original

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        pos = [0] * n
        cur_max = 0
        cnt = 0
        
        while True:
            for i in range(n):
                while pos[i] < m and mat[i][pos[i]] < cur_max:
                    pos[i] += 1
                if pos[i] >= m:
                    return -1
                if mat[i][pos[i]] != cur_max:
                    cnt = 1
                    cur_max = mat[i][pos[i]]
                else:
                    cnt += 1
                    if cnt == n:
                        return cur_max

Go solution

matched/original

func smallestCommonElement(mat [][]int) int {
    n := len(mat)
    m := len(mat[0])
    pos := make([]int, n)
    cur_max := 0
    cnt := 0

    for {
        for i := 0; i < n; i++ {
            for pos[i] < m && mat[i][pos[i]] < cur_max {
                pos[i]++
            }
            if pos[i] >= m {
                return -1
            }
            if mat[i][pos[i]] != cur_max {
                cnt = 1
                cur_max = mat[i][pos[i]]
            } else {
                cnt++
                if cnt == n {
                    return cur_max
                }
            }
        }
    }
}

Explanation

Algorithm

1⃣Инициализация переменных:

Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.

2⃣Итерация по строкам матрицы:

Для каждой строки:

- увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума.

- если достигли конца строки, возвращайте -1.

- если значение равно текущему максимуму, увеличивайте счетчик.

- в противном случае, сбросьте счетчик до 1 и обновите текущий максимум.

3⃣Проверка счетчика:

Если счетчик равен количеству строк, возвращайте текущий максимум.

Повторите шаг 2.

😎