Is Find Smallest Common Element in All Rows easy or hard?

The problem is rated Medium because the idea is simple but requires recognizing how to efficiently check presence across multiple rows. A naive scan works but is slow, while the optimal counting solution processes the matrix once and uses frequency tracking.

Find Smallest Common Element in All Rows Python/Java solution

In Python or Java, implement a counting array or HashMap to track how many rows contain each value. Iterate through the matrix and update the count for each element. When a value's count equals the total number of rows, return it as the smallest common element. The implementation runs in O(m * n) time.

How to solve Find Smallest Common Element in All Rows in O(m*n)?

Use a frequency counter while scanning the matrix. For every value encountered, increment its count in an array or hash map. When the count reaches the total number of rows, that value exists in every row. Track the minimum such value while iterating to ensure the smallest common element is returned.

What is the best approach for Find Smallest Common Element in All Rows?

The counting (frequency tracking) approach is typically the best solution. Traverse every element in the matrix and maintain a count of how many rows contain each value. When a value's frequency equals the number of rows, it appears in every row. This runs in O(m * n) time and avoids repeated searches.

Is Find Smallest Common Element in All Rows asked at Google/Amazon/Meta?

Matrix traversal and frequency-counting problems like this appear in interviews at large tech companies including Google, Amazon, and Meta. The problem tests understanding of sorted structures, hash-based counting, and efficient scanning of 2D arrays.

What data structure is used in Find Smallest Common Element in All Rows?

The main data structure is a frequency counter implemented using either a hash table or a fixed-size counting array. The matrix itself is traversed row by row. Some alternative solutions also use binary search on sorted rows.

What is the time complexity of Find Smallest Common Element in All Rows?

The optimal counting solution runs in O(m * n) time where m is the number of rows and n is the number of columns. Each matrix element is processed once. Space complexity is O(1) if a fixed-size counting array is used, since values are bounded by the problem constraints.

Description Hints 4 Solution Video 13:03

1198. Find Smallest Common Element in All Rows

Medium76.5% acceptance2 companiesPremium elsewhere, free here

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: 5

Example 2:

Input: mat = [[1,2,3],[2,3,4],[2,3,5]]
Output: 2

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 500
1 <= mat[i][j] <= 10⁴
mat[i] is sorted in strictly increasing order.

Asked at 2 companies

Microsoft Amazon

Topics

Hints open one at a time

Hint 1

Notice that each row has no duplicates.

Hint 2

Is counting the frequency of elements enough to find the answer?

Hint 3

Use a data structure to count the frequency of elements.

Hint 4

Find an element whose frequency equals the number of rows.

13:03

Still stuck?Read the written solution, or watch a walkthrough.

Open solution