1198. Find Smallest Common Element in All Rows

Description

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.

Constraints

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 500

• 1 <= mat[i][j] <= 104

• mat[i] is sorted in strictly increasing order.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : O(MNlogN). We iterate through m elements in the first row. 
 *    For each element, we perform the binary search n times over m elements.
 * Space complexity : O(1)
 */

class Solution {
    public int smallestCommonElement(int[][] mat) {
        if(mat == null || mat.length == 0 || mat[0].length == 0) {
            return -1;
        }
        
        int row = mat.length, col = mat[0].length;
        int count = 0, min = Integer.MAX_VALUE;
        
        for(int j = 0; j < col; j++) {
            count = 1;
            for(int i = 1; i < row; i++) {
                if(binarySearch(mat[i], mat[0][j]) == -1) {
                    break;
                } else {
                    count++;
                }
            }
            if(count == row && mat[0][j] < min) {
                min = mat[0][j];
            }
        }
        
        return min == Integer.MAX_VALUE? -1: min;
    }
    
    private int binarySearch(int[] arr, int target) {
        int low = 0, high = arr.length-1;
        while(low <= high) {
            int mid = (low + high) / 2;
            if(arr[mid] == target) {
                return mid;
            }
            if(target > arr[mid]) {
                low = mid + 1;
            } else {
                high = mid-1;
            }
        }
        return -1;
    }
}

Solution 2

Follow up