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

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

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

/**
 * Time complexity : O(MN). we iterate through all MN elements in the matrix 
 *    in the worst case.
 * Space complexity : O(M), M is the row size. To store row indices.
 */

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 = 0;
        
        int[] pos = new int[row];
        
        while(true) {
            for(int i = 0; i < row; i++) {
                while(pos[i] < col && mat[i][pos[i]] < min) {
                    pos[i]++;
                }
                if(pos[i] >= col) {
                    return -1;
                }
                
                count++;
                
                if(mat[i][pos[i]] != min) {
                    count = 1;
                    min = mat[i][pos[i]];
                } else if(count == row) {
                    return min;
                }
            }
        }
    }
}

Follow up