LC: 1198. Find Smallest Common Element in All Rows
https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
1198. Find Smallest Common Element in All Rows
Given an m x n matrix mat where every row is sorted in strictly increasing order, return the smallest common element in all rows.
If there is no common element, 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: 5Example 2:
Input: mat = [[1,2,3],[2,3,4],[2,3,5]]
Output: 2Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 5001 <= mat[i][j] <= 104mat[i]is sorted in strictly increasing order.
1198. Find Smallest Common Element in All Rows:
The Essence:
Die kleinste gemeinsame Zahl muss vor allem bei der ersten Zeile zu finden sein. Man kann also von der ersten Zahl der ersten Zeile anfangen und in jeder anderen Zeile die Anwesenheit dieser Zahl bestätigen. Wenn es nicht der Fall ist, kann man die nächste, größere Zahl aus der ersten Zeile suchen.
Details:
Für die Suche kann man binäre Suche verwenden, weil alle Zeilen der Matrix sortiert sind.
Solution(s):
Default Code:
Last updated