Example: Find Common Element Using Row Pointers in C++

// Find Common Element Using Row Pointers
#include <iostream>
#include <vector>
#include <climits> // For INT_MIN
#include <algorithm> // For std::max

using namespace std;

// Function to find common element using row pointers
int findCommonElement_Pointers(const vector<vector<int>>& matrix) {
    int R = matrix.size();
    if (R == 0) return -1;

    int C = matrix[0].size();
    if (C == 0) return -1;

    // Initialize an array of pointers (indices) for each row
    // Each pointer points to the last element of its respective row
    vector<int> col_pointers(R);
    for (int i = 0; i < R; ++i) {
        col_pointers[i] = C - 1; // Start from the last column
    }

    // Loop until one of the pointers goes out of bounds
    while (true) {
        // Find the maximum element among all elements pointed to by col_pointers
        int max_val = INT_MIN;
        for (int i = 0; i < R; ++i) {
            max_val = max(max_val, matrix[i][col_pointers[i]]);
        }

        // Check if all elements pointed to are equal to max_val
        bool all_equal = true;
        for (int i = 0; i < R; ++i) {
            if (matrix[i][col_pointers[i]] < max_val) {
                // If an element is smaller than max_val, move its pointer left
                col_pointers[i]--;
                all_equal = false; // Not all elements are equal yet
            }
            // If any pointer goes out of bounds, no common element exists
            if (col_pointers[i] < 0) {
                return -1;
            }
        }
        
        // If all elements pointed to are equal, that's our common element
        if (all_equal) {
            return matrix[0][col_pointers[0]]; // Any row's pointer will do, since they are all equal
        }
    }
}

int main() {
    // Step 1: Define sample matrices
    vector<vector<int>> matrix1 = {
        {1, 2, 3, 4, 5},
        {2, 3, 4, 5, 6},
        {3, 4, 5, 6, 7},
        {4, 5, 6, 7, 8}
    };
    cout << "Matrix 1:" << endl;
    for (const auto& row : matrix1) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "Common element (Pointers): " << findCommonElement_Pointers(matrix1) << endl << endl;

    vector<vector<int>> matrix2 = {
        {1, 2, 3, 4},
        {1, 2, 3, 4},
        {1, 2, 3, 4}
    };
    cout << "Matrix 2:" << endl;
    for (const auto& row : matrix2) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "Common element (Pointers): " << findCommonElement_Pointers(matrix2) << endl << endl;

    vector<vector<int>> matrix3 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    cout << "Matrix 3:" << endl;
    for (const auto& row : matrix3) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "Common element (Pointers): " << findCommonElement_Pointers(matrix3) << endl << endl;

    vector<vector<int>> matrix4 = {
        {1, 2, 3, 4},
        {2, 3, 4, 5},
        {3, 4, 5, 6}
    };
    cout << "Matrix 4:" << endl;
    for (const auto& row : matrix4) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "Common element (Pointers): " << findCommonElement_Pointers(matrix4) << endl << endl;

    return 0;
}