Count Unique Elements in Each Row of a Matrix in C++

To count unique elements in each row of a matrix in C++, the most robust approach involves iterating through each row and inserting its values into a std::set. Since sets automatically handle duplicates by storing only distinct keys, the size of the set after populating it with a single row directly corresponds to the number of unique elements. This method leverages standard library containers to avoid manual duplicate-checking logic, ensuring both correctness and readability for general-purpose applications.

Understanding the Core Logic

The fundamental challenge in this problem is distinguishing between identical values within a specific row. A naive approach might involve nested loops comparing every element against every other element in the same row, resulting in an O(N^2) complexity per row. While acceptable for very small matrices, this becomes inefficient as dimensions grow. Using a std::set or std::unordered_set reduces the average time complexity to O(N log N) or O(N) respectively, where N is the number of columns. When you iterate through a row, you are essentially collecting a stream of integers (or other comparable types). The std::set container uses a balanced binary search tree (typically a Red-Black Tree) under the hood. Every time you call insert(), the container checks if the value already exists. If it does, the insertion is ignored; if it does not, the new value is added. By the end of the iteration over a single row, the .size() method returns the exact count of unique entries. For example, consider a row containing the values [1, 2, 2, 3]. 1. Insert 1: Set contains {1}. Size is 1. 2. Insert 2: Set contains {1, 2}. Size is 2. 3. Insert 2: Duplicate detected. Set remains {1, 2}. Size is still 2. 4. Insert 3: Set contains {1, 2, 3}. Size is 3. The final result is 3, which is the correct count of unique elements. This logic applies uniformly across all rows in the matrix.

Implementation Strategy

To implement this efficiently, you should separate the logic into a function that processes a single vector (representing one row) and then iterate over your main data structure. This modular design improves testability and code clarity. You can use std::vector> to represent the 2D matrix. Here is the step-by-step implementation plan:

• Include Necessary Headers: Ensure you include <iostream>, <vector>, and <set>.
• Define a Helper Function: Create a function countUniqueInRow that takes a const std::vector& and returns an int.
• Populate the Set: Inside the helper, declare a std::set<int> and insert all elements from the input vector.
• Return Size: Return the .size() of the set.
• Process the Matrix: In main, loop through each row of the matrix and call the helper function.

This approach ensures that you do not reinvent the wheel. Standard library containers are highly optimized and less prone to off-by-one errors than custom sorting or hashing algorithms. For more insights on efficient pointer usage and performance optimization in similar contexts, you might find Faster C++: Understanding Pointer Usage in Leetcode helpful, although using vectors and sets here abstracts away low-level pointer management.

Complete Code Example

Below is a complete, compilable example demonstrating the solution. It defines a matrix, processes each row, and prints the results.

#include <iostream>
#include <vector>
#include <set>

// Function to count unique elements in a single row
int countUniqueInRow(const std::vector<int>& row) {
    std::set<int> uniqueElements;
    for (int num : row) {
        uniqueElements.insert(num);
    }
    return uniqueElements.size();
}

int main() {
    // Define a 2D matrix (vector of vectors)
    std::vector<std::vector<int>> matrix = {
        {1, 2, 2, 3},
        {4, 4, 4, 4},
        {5, 6, 7, 8},
        {9, 9, 10, 10}
    };

    // Iterate through each row and print the count of unique elements
    for (size_t i = 0; i < matrix.size(); ++i) {
        int uniqueCount = countUniqueInRow(matrix[i]);
        std::cout << "Row " << i << ": " << uniqueCount << " unique elements." << std::endl;
    }

    return 0;
}

In this code, the outer loop iterates over the rows of the matrix. For each row, the countUniqueInRow function creates a fresh std::set, inserts all elements, and returns the count. The output will be: Row 0: 3 unique elements. Row 1: 1 unique element. Row 2: 4 unique elements. Row 3: 2 unique elements.

Performance Considerations

While std::set is convenient, it has overhead due to dynamic memory allocation for each node in the tree. If you are dealing with extremely large matrices or real-time systems where latency is critical, std::unordered_set might be faster because it uses hash tables, offering average O(1) insertion times. However, unordered_set requires the elements to be hashable, which is true for integers but may require custom hashers for complex objects. Another alternative is sorting the row in place and counting adjacent differences. This avoids extra memory allocation for the set nodes but modifies the original data unless you copy the row first. Sorting takes O(N log N) time, similar to std::set, but often has better cache locality and lower constant factors. If memory is constrained, you can use a boolean array or bitset if the range of values in the matrix is known and small. For example, if all elements are between 0 and 100, a bool seen[101] array can track presence without any dynamic allocation. This approach runs in O(N) time and O(K) space, where K is the range of values. For further reading on managing resources and avoiding lifetime issues in complex C++ structures, refer to Understanding Lifetime Issue Instance of Class. This knowledge helps prevent bugs when objects go out of scope unexpectedly during matrix operations.

Frequently Asked Questions

Can I use std::vector instead of std::set?

You can use a vector, but you must manually remove duplicates before counting. Typically, this involves sorting the vector and using std::unique followed by erase. This adds several lines of code compared to the set approach.

Is std::unordered_set faster than std::set?

Generally, yes, because unordered_set provides average O(1) insertion time compared to O(log N) for set. However, unordered_set has higher constant overhead and worst-case O(N) performance if hash collisions occur frequently.

What if my matrix contains floating-point numbers?

std::set works with floats, but precision issues may arise. Two floats that appear equal might differ slightly in binary representation. It is safer to round them or use a tolerance-based comparison if exact equality is not guaranteed.

How do I handle empty rows in the matrix?

If a row is empty, the loop over the row will not execute, the set will remain empty, and .size() will return 0. This is the correct behavior for counting unique elements in an empty collection.

Does this method preserve the order of elements?

No, std::set stores elements in sorted order. If you need to preserve the original order while counting unique items, you would need to use a std::vector alongside a std::set for tracking seen items, or use std::unordered_set if order preservation is not required but speed is.