C++ Program To Find A Common Element In All Rows Of A Given Row Wise Sorted Matrix

Finding common elements across multiple data sets is a frequent task in data processing. When dealing with a matrix where each row is sorted, we can develop efficient algorithms to identify an element that appears in every single row. In this article, you will learn how to find such a common element in a row-wise sorted matrix using C++.

Problem Statement

Given an M x N matrix where each row is sorted in ascending order, the challenge is to find a common element that exists in *all* rows. If multiple common elements exist, any one of them is acceptable. If no such element exists, the program should indicate that. This problem often arises in scenarios like database query optimization or analyzing sensor data where each sensor (row) reports sorted readings.

Example

Consider the following 3 x 4 matrix:

{{1, 2, 3, 4},
 {1, 2, 3, 4},
 {1, 2, 3, 4}}

A common element is 1 (or 2, 3, or 4).

Another example:

{{1, 2, 3, 4},
 {2, 3, 4, 5},
 {3, 4, 5, 6}}

A common element is 3 (or 4).

Background & Knowledge Prerequisites

To understand the solutions presented, you should have a basic understanding of:

• C++ fundamentals: variables, loops, conditional statements.
• Arrays and two-dimensional arrays (matrices).
• Standard Template Library (STL) containers: vector and unordered_map (for the hashing approach).
• Basic algorithm complexity analysis (optional but helpful).

Use Cases or Case Studies

1. Database Query Optimization: If you're joining multiple tables where relevant columns are sorted, quickly finding common values can significantly speed up join operations.
2. Sensor Data Analysis: When multiple sensors report sorted data streams (e.g., temperature readings over time), identifying a temperature value recorded by all sensors at some point could indicate widespread environmental conditions.
3. Genomic Sequencing: In bioinformatics, finding common sequence patterns (elements) across multiple sorted genetic sequences can point to conserved regions or shared genetic traits.
4. Supply Chain Management: Identifying a product ID that appears in the sorted inventory lists of all warehouses indicates a universally stocked item.
5. Log File Analysis: If multiple system logs are sorted by timestamps, finding a specific error code or event ID that occurred in all logs can help diagnose system-wide issues.

Solution Approaches

Approach 1: Using a Frequency Map (Hashing)

This approach iterates through each row and uses a hash map to count the occurrences of each element. An element found in M rows (where M is the total number of rows) is a common element. This method doesn't fully exploit the sorted property but is general and relatively efficient.

One-line summary: Use a hash map to store element counts across all rows; if an element's count equals the number of rows, it's common.

Code example:

// Find Common Element Using Hashing
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

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

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

    unordered_map<int, int> counts; // Map to store element counts

    // Add elements of the first row to the map with count 1
    for (int j = 0; j < C; ++j) {
        counts[matrix[0][j]] = 1;
    }

    // Iterate through the remaining rows (from the second row)
    for (int i = 1; i < R; ++i) {
        // Iterate through elements of the current row
        for (int j = 0; j < C; ++j) {
            // If the element is present in the map and its count matches the current row index
            // This ensures we count each unique occurrence from distinct rows.
            // Example: If counts[x] == i, it means x was found in rows 0 to i-1.
            // Now if we find x in row i, its count can be incremented to i+1.
            if (counts.count(matrix[i][j]) && counts[matrix[i][j]] == i) {
                counts[matrix[i][j]]++;
            }
        }
    }

    // Check which element has a count equal to the number of rows
    for (auto const& pair : counts) {
        if (pair.second == R) {
            return pair.first; // Found a common element
        }
    }

    return -1; // No common element found
}

int main() {
    // Step 1: Define a sample matrix
    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 (Hashing): " << findCommonElement_Hashing(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 (Hashing): " << findCommonElement_Hashing(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 (Hashing): " << findCommonElement_Hashing(matrix3) << endl << endl;

    return 0;
}

Run

Sample output:

Matrix 1:
1 2 3 4 5 
2 3 4 5 6 
3 4 5 6 7 
4 5 6 7 8 
Common element (Hashing): 4 

Matrix 2:
1 2 3 4 
1 2 3 4 
1 2 3 4 
Common element (Hashing): 1 

Matrix 3:
1 2 3 
4 5 6 
7 8 9 
Common element (Hashing): -1

Stepwise explanation:

1. Initialize an unordered_map called counts to store the frequency of elements across rows.
2. Iterate through the first row of the matrix. For each element in the first row, add it to counts with a value of 1. This marks that these elements have been seen in the first row.
3. For subsequent rows (from index 1 to R-1):

• Iterate through each element matrix[i][j] in the current row i.
• Check if matrix[i][j] is present in the counts map AND if its current count is exactly i. This specific check ensures that the element was present in all previous rows (0 to i-1) but hasn't yet been counted for the current row i.
• If both conditions are true, increment counts[matrix[i][j]] by 1. This indicates that the element has now been found in i+1 rows.

1. After processing all rows, iterate through the counts map. If any element has a count equal to the total number of rows (R), that element is a common element in all rows. Return it.
2. If no such element is found, return -1.

Approach 2: Optimized using Row Pointers (Leveraging Sorted Property)

This is the most efficient approach for a row-wise sorted matrix. It uses a pointer (index) for each row, starting from the last element of each row. In each step, it finds the maximum of these elements and tries to make all elements equal to this maximum by moving pointers in rows where the element is smaller.

One-line summary: Use a pointer for each row, starting from the end. In each step, find the maximum element pointed to by all pointers and move pointers in rows where the current element is smaller than this maximum.

Code example:

// 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;
}

Run

Sample output:

Matrix 1:
1 2 3 4 5 
2 3 4 5 6 
3 4 5 6 7 
4 5 6 7 8 
Common element (Pointers): 4 

Matrix 2:
1 2 3 4 
1 2 3 4 
1 2 3 4 
Common element (Pointers): 4 

Matrix 3:
1 2 3 
4 5 6 
7 8 9 
Common element (Pointers): -1 

Matrix 4:
1 2 3 4 
2 3 4 5 
3 4 5 6 
Common element (Pointers): 3

Stepwise explanation:

1. Initialize a col_pointers vector, where col_pointers[i] will store the current column index for row i. Initially, all pointers are set to C - 1 (the last column of each row).
2. Enter a while(true) loop, which will continue until a common element is found or it's determined that none exist.
3. Find the maximum value: In each iteration, find the maximum element among all elements currently pointed to by col_pointers. Let this be max_val.
4. Check for equality and move pointers:

• Initialize a boolean flag all_equal to true.
• Iterate through each row i from 0 to R-1.
• If matrix[i][col_pointers[i]] (the element in the current row i at its pointed-to column) is less than max_val:
• Decrement col_pointers[i]. This moves the pointer for row i one step to the left (towards smaller elements), because we need to find a value at least max_val in this row.
• Set all_equal to false.
• Boundary Check: After potentially decrementing, if col_pointers[i] becomes less than 0, it means we have exhausted all elements in that row and haven't found a common element. In this case, no common element exists, so return -1.

1. Common element found: If after iterating through all rows, all_equal is still true, it means all elements pointed to by col_pointers are now equal to max_val. This max_val is the common element in all rows. Return it.

This process essentially tries to converge all pointers to the same value. By always moving the pointer of the row with the smallest current element, it effectively "pushes" towards a common ground or exhausts rows if no common element can be found.

Conclusion

Finding a common element in a row-wise sorted matrix is a classic problem with various practical applications. While a hashing-based approach provides a general solution, leveraging the sorted property of the matrix rows with a multi-pointer strategy offers a significantly more optimized and elegant solution. The choice between approaches often depends on the specific constraints of the problem and the need to balance simplicity with performance.

Summary

• Problem: Find an element present in all rows of a row-wise sorted matrix.
• Hashing Approach:
• Uses unordered_map to count occurrences of elements.
• Iterates through rows, incrementing counts for elements seen in successive rows.
• Identifies elements whose count equals the total number of rows.
• General, but doesn't fully exploit sorted property.
• Optimized Pointer Approach:
• Uses an index (pointer) for each row, starting from the last element.
• Continuously finds the maximum element among all pointed-to elements.
• Moves pointers of rows whose elements are smaller than the maximum to the left.
• Returns the element when all pointers converge to the same value.
• Highly efficient due to leveraging the sorted property.
• Key takeaway: Utilizing data structure properties (like sorted rows) can lead to significantly more efficient algorithms.