Find Smallest Common Element in All Rows - Practice Coding Problems

Find Smallest Common Element in All Rows - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11]]

› Output: 5

💡 Note: Element 5 appears in all three rows: row 0 at index 4, row 1 at index 2, and row 2 at index 1. It's the smallest such common element.

Example 2 — No Common Element

$ Input: mat = [[1,2,3],[4,5,6],[7,8,9]]

› Output: -1

💡 Note: No element appears in all three rows. Each row has completely different elements, so return -1.

Example 3 — Multiple Common Elements

$ Input: mat = [[1,2,3,4,5],[1,3,5,7,9],[1,4,5,8,9]]

› Output: 1

💡 Note: Elements 1 and 5 appear in all rows, but 1 is smaller than 5, so return 1.

Constraints

1 ≤ m, n ≤ 500
1 ≤ mat[i][j] ≤ 10⁴
mat[i] is sorted in strictly increasing order

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Each row is sorted in increasing order

Search Process

Check which elements appear in all rows

Result

Return the smallest common element or -1

Key Takeaway

🎯 Key Insight: Use the sorted property of rows with binary search to efficiently find common elements

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is to leverage the sorted property of each row. Start with elements from the first row as candidates and efficiently check their presence in other rows using binary search. The binary search approach provides optimal performance with Time: O(n × m × log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(n × m × log n)	O(1)	Use binary search to check if elements from first row exist in other rows
Frequency Count with Hash Map	O(m × n)	O(m × n)	Count frequency of each element, return smallest with full count
Brute Force - Check Each Element	O(m × n²)	O(1)	For each element in first row, check if it exists in all other rows

Binary Search Optimization — Algorithm Steps

Take each element from first row as candidate
Use binary search to check existence in each other row
Return first element found in all rows

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Candidate

Take element from first row

Binary Search

Use binary search in each other row

Found or Continue

If found in all rows, return; else try next

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool binarySearch(int* arr, int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return true;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

int solution(int** mat, int matSize, int* matColSize) {
    if (matSize == 0 || matColSize[0] == 0) return -1;
    
    int m = matSize, n = matColSize[0];
    
    // Check each element in first row
    for (int j = 0; j < n; j++) {
        int candidate = mat[0][j];
        bool foundInAll = true;
        
        // Check if this element exists in all other rows using binary search
        for (int i = 1; i < m; i++) {
            if (!binarySearch(mat[i], matColSize[i], candidate)) {
                foundInAll = false;
                break;
            }
        }
        
        if (foundInAll) return candidate;
    }
    
    return -1;
}

int main() {
    // Simplified parsing - assume valid input format
    int mat1[] = {1, 2, 3, 4, 5};
    int mat2[] = {2, 4, 5, 8, 10};
    int mat3[] = {3, 5, 7, 9, 11};
    int* mat[] = {mat1, mat2, mat3};
    int matColSize[] = {5, 5, 5};
    
    printf("%d\n", solution(mat, 3, matColSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × log n)

For each of n elements in first row, binary search in m-1 other rows takes log n time

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for binary search

✓ Linear Space

52.4K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler