Raghav - 2 months ago 5x
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()){
rtn.insert(iter->second);
rtn.insert(i);
}
dup.insert(std::make_pair(*first, i));
++i;
++first;
}
return {rtn.begin(), rtn.end()};
}
``````

Explanation:

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

Outputs

``````1 0
``````

Again,

For an input of:

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

Outputs

``````7 0 5 1 6
``````

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

Source (Stackoverflow)