Raghav Raghav - 4 months ago 30
C++ Question

How to find duplicate elements' index in C++?

Is there any STL function in C++ that allows me to find all indices of duplicates in an array?

For eg:

int array[] = {1,1,2,3,4};

Should return 0,1


Assuming you cannot modify the array by sorting, efficiently, you could use a std::unordered_set and unordered_map. This does it in O(N) + O(1) + O(1):

template<typename Iter>
std::vector<int> duplicate_indices(Iter first, Iter last){
    std::unordered_set<int> rtn;
    std::unordered_map<int, int> dup;
    std::size_t i = 0;
    while(first != last){
        auto iter = dup.find(*first);
        if(iter != dup.end()){
        dup.insert(std::make_pair(*first, i));
    return {rtn.begin(), rtn.end()};


Given an array A

  • Using a set of unique indices, rtn.
  • Using a KV map, dup; where k is an element in the array A, and v is the index of that element in the array.

  • For Each item, a with index i in the array, find kv if the item exists as k in dup.

    • If it doesn't exist,
      • Add i to rtn
      • Add v to rtn
    • Else, add a and i as kv into dup
  • return rtn

See a full example live here.

For an input of:

int array[] = {1,1,2,3,4};


1 0


For an input of:

int array[] = {1, 1, 2, 3, 4, 1, 0, 0, 9};


7 0 5 1 6

If you need the indices in order, you could simply sort the resulting array.