Common Element in all Rows of a Given Row-Wise Sorted Matrix

We are given a matrix where every row is sorted in increasing order. Our task is to find and return a common element in all rows. If there is no common element, then returns -1. 

Example 1 

Input:

mat[][] = { { 1, 3, 5, 7 },

                { 2, 4, 6, 8 },

                { 3, 5, 7, 9 } };

Output: -1

Explanation: There is no common element in all rows.

Example 2

Input:

mat[][] = { { 2, 3, 4, 8 },

                { 3, 4, 7, 9 },

                { 4, 6, 8, 10 } };

Output: 4

Explanation: The common element in all rows is 4.

Approach

We are given a matrix where each row is sorted in increasing order. The task is to find and return a common element that exists in all rows of the matrix. To achieve this, we iterate through the elements of the first row and check if each element is present in all subsequent rows. If an element is found to be present in all rows, we return it as the common element. If no common element is found, we return -1.

Steps

1. Initialize a boolean array, presentInRow, of size equal to the number of columns in the matrix. This array will be used to track whether an element is present in each row.
2. Iterate over the elements of the first row of the matrix.
3. For each element in the first row, check if it exists in all subsequent rows.
4. If an element is found to be present in all rows, return it as the common element.
5. If no common element is found after iterating over all elements in the first row, return -1.

Complexity

• Time Complexity: O(M * N), where M is the number of rows and N is the number of columns in the matrix.
• Space Complexity: O(1)

Code

#Java Code

public class CommonElementFinder {

    public static int findCommonElement(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        // Boolean array to track presence of an element in each row
        boolean[] presentInRow = new boolean[n];

        // Initialize presentInRow with true for elements in the first row
        for (int j = 0; j < n; j++) {
            presentInRow[j] = true;
        }

        // Iterate over elements of the first row
        for (int j = 0; j < n; j++) {

            int element = mat[0][j];
            boolean presentInAllRows = true;

            // Check if the element exists in all subsequent rows
            for (int i = 1; i < m; i++) {
                boolean found = false;
                for (int k = 0; k < n; k++) {
                    if (mat[i][k] == element) {
                        found = true;
                        break;
                    }
                }

                if (!found) {
                    presentInAllRows = false;
                    break;
                }
            }

            // If the element is present in all rows, return it
            if (presentInAllRows) {
                return element;
            }
        }

        // If no common element is found, return -1
        return -1;
    }


    public static void main(String[] args) {

        // example 1
        int[][] mat1 = {
            { 1, 3, 5, 7 },
            { 2, 4, 6, 8 },
            { 3, 5, 7, 9 }
        };
        int commonElement1 = findCommonElement(mat1);
        System.out.println("Example 1");

        if (commonElement1 != -1) {
            System.out.println("Common Element: " + commonElement1);
        } else {
            System.out.println("No common element found.");
        }

        // example 2
        int[][] mat2 = {
            { 2, 3, 4, 8 },
            { 3, 4, 7, 9 },
            { 4, 6, 8, 10 }
        };
        int commonElement2 = findCommonElement(mat2);
        System.out.println("Example 2");

        if (commonElement2 != -1) {
            System.out.println("Common Element: " + commonElement2);
        } else {
            System.out.println("No common element found.");
        }

    }

}

Output

Example 1
No common element found.
Example 2
Common Element: 4